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

DOI10.1007/978-3-030-43662-9_18MaRDI QIDQ5098783zbMATH OpenOpenAlexFDO

Authors Oded Goldreich, Guy N. Rothblum

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)

Recommendations

• scientific article; zbMATH DE number 512981
• On constant-round concurrent non-malleable proof systems
• On doubly-efficient interactive proof systems
• How to construct constant-round zero-knowledge proof systems for NP
• Constant-round interactive proofs for delegating computation
• Constant-round interactive proofs for delegating computation
• Interactive proof systems and alternating time-space complexity
• scientific article; zbMATH DE number 176510
• Interactive proofs with approximately commuting provers
• A PCP theorem for interactive proofs and applications

Cites work

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

Cited in

(4)

• Doubly efficient interactive proofs over infinite and non-commutative rings
• Improved Merlin-Arthur protocols for central problems in fine-grained complexity
• Constant-round arguments from one-way functions
• Beyond MPC-in-the-head: black-box constructions of short zero-knowledge proofs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5098783)