Semi-Streaming Algorithms for Annotated Graph Streams

DOI10.4230/LIPIcs.ICALP.2016.59zbMath1388.68137arXiv1407.3462OpenAlexW2963869517MaRDI QIDQ4598198

Justin Thaler

Publication date: 19 December 2017

Full work available at URL: https://arxiv.org/abs/1407.3462

zbMATH Keywords

probabilistic proof systemsannotated data streamsgraph streamsstream verification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A Hierarchy Theorem for Interactive Proofs of Proximity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An Exponential Separation Between MA and AM Proofs of Proximity ⋮ Approximate F_2-Sketching of Valuation Functions ⋮ An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity ⋮ Non-interactive proofs of proximity ⋮ Unnamed Item ⋮ Optimality of linear sketching under modular updates ⋮ Verifiable Stream Computation and Arthur--Merlin Communication