Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation

DOI10.4230/LIPICS.CCC.2016.2MaRDI QIDQ5368736zbMATH OpenFDO

Authors Ryan Williams

Publication date 10 October 2017

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

zbMATH Keywords

counting complexityexponential-time hypothesisinteractive proofsMerlin-Arthur games

Mathematics Subject Classification ID

Complexity of proofs (03F20) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Time-optimal interactive proofs for circuit evaluation
• Circuit lower bounds for Merlin-Arthur classes
• Circuit lower bounds for Merlin-Arthur classes
• Linear-time zero-knowledge proofs for arithmetic circuit satisfiability
• Polynomial time interactive proofs for linear algebra with exponential matrix dimensions and scalars given by polynomial time circuits

Cited in

(20)

• Proofs of Work from worst-case assumptions
• Efficiently enumerating hitting sets of hypergraphs arising in data profiling
• Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
• A short note on Merlin-Arthur protocols for subset sum
• Towards hardness of approximation for polynomial time problems
• A hierarchy theorem for interactive proofs of proximity
• Simple doubly-efficient interactive proof systems for locally-characterizable sets
• Fine-grained derandomization: from problem-centric to resource-centric complexity
• On nondeterministic derandomization of Freivalds' algorithm: consequences, avenues and algorithmic progress
• The Orthogonal Vectors Conjecture for Branching Programs and Formulas
• Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
• How proofs are prepared at Camelot (extended abstract)
• On the complexity of compressing obfuscation
• Improved Merlin-Arthur protocols for central problems in fine-grained complexity
• When Arthur has neither random coins nor time to spare: superfast derandomization of proof systems
• Lattice problems beyond polynomial time
• Nearly optimal pseudorandomness from hardness
• Towards permissionless consensus in the standard model via fine-grained complexity
• Polynomial formulations as a barrier for reduction-based hardness proofs
• On exponential-time hypotheses, derandomization, and circuit lower bounds

This page was built for publication: Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation

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