Constant-Round Interactive Proof Systems for AC0[2] and NC1

DOI10.1007/978-3-030-43662-9_18OpenAlexW2799247293MaRDI QIDQ5098783

Guy N. Rothblum, Oded Goldreich

Publication date: 30 August 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-43662-9_18

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Related Items (1)

Improved Merlin-Arthur protocols for central problems in fine-grained complexity

Cites Work

• Unnamed Item
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• On uniformity within \(NC^ 1\)
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Delegating Computation
• Interactive PCP
• The Knowledge Complexity of Interactive Proof Systems
• Simple Constructions of Almost k-wise Independent Random Variables
• Algebraic methods for interactive proof systems
• IP = PSPACE
• Faster all-pairs shortest paths via circuit complexity
• Constant-round interactive proofs for delegating computation
• Computational Complexity

This page was built for publication: Constant-Round Interactive Proof Systems for AC0[2] and NC1