Simple doubly-efficient interactive proof systems for locally-characterizable sets
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 5485522 (Why is no real title available?)
- Algebraic methods for interactive proof systems
- Arthur-Merlin streaming complexity
- Average-case fine-grained hardness
- Computational Complexity
- Constant-round interactive proofs for delegating computation
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- How proofs are prepared at Camelot (extended abstract)
- IP = PSPACE
- Invariance in property testing
- Losing weight by gaining edges
- Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
- On the possibility of faster \textsc{SAT} algorithms
- PP is as Hard as the Polynomial-Time Hierarchy
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- Semi-streaming algorithms for annotated graph streams
- Simple Constructions of Almost k-wise Independent Random Variables
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation
- The Knowledge Complexity of Interactive Proof Systems
- Tight lower bounds for certain parameterized NP-hard problems
- Towards polynomial lower bounds for dynamic problems
Cited in
(7)- Constant-Round Interactive Proof Systems for AC0[2] and NC1
- Worst-Case to Average-Case Reductions for Subclasses of P
- Fine-grained secure computation
- Improved Merlin-Arthur protocols for central problems in fine-grained complexity
- Doubly efficient interactive proofs over infinite and non-commutative rings
- On doubly-efficient interactive proof systems
- Proofs of Work from worst-case assumptions
This page was built for publication: Simple doubly-efficient interactive proof systems for locally-characterizable sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993281)
