Verifiable Stream Computation and Arthur--Merlin Communication

DOI10.1137/17M112289XzbMath1430.68114OpenAlexW2963613988MaRDI QIDQ5232326

Justin Thaler, Suresh Venkatasubramanian, Amit Chakrabarti, Andrew McGregor, Graham Cormode

Publication date: 2 September 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/17m112289x

zbMATH Keywords

probabilistic proof systemsArthur-Merlin communication complexitystreaming interactive proofs

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other nonclassical models of computation (68Q09) Communication complexity, information complexity (68Q11)

Cites Work

• Quantum information and the PCP theorem
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• The space complexity of approximating the frequency moments
• Lower bounds for one-way probabilistic communication complexity and their application to space complexity
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
• Streaming graph computations with a helpful advisor
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• Practical verified computation with streaming interactive proofs
• Time-Optimal Interactive Proofs for Circuit Evaluation
• Algebrization
• Streaming computations with a loquacious prover
• Streaming Verification in Data Analysis
• Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams
• The Probabilistic Communication Complexity of Set Intersection
• Rounds in Communication Complexity Revisited
• Algebraic methods for interactive proof systems
• IP = PSPACE
• Semi-Streaming Algorithms for Annotated Graph Streams
• The Landscape of Communication Complexity Classes.
• Streaming Verification of Graph Properties.
• Streaming Authenticated Data Structures
• Annotations in Data Streams
• Memory Delegation
• Advances in Cryptology - EUROCRYPT 2004
• Arthur-Merlin Streaming Complexity
• Annotations for Sparse Data Streams
• Probability and Computing
• Majority Gate Networks
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Verifiable Stream Computation and Arthur--Merlin Communication