Short PCPs with Projection Queries

DOI10.1007/978-3-662-43948-7_14zbMath1410.68135MaRDI QIDQ5167739

Emanuele Viola, Eli Ben-Sasson

Publication date: 1 July 2014

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-43948-7_14

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Unnamed Item, New algorithms and lower bounds for circuits with linear threshold gates, Unnamed Item, Unnamed Item, On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection, Quantified Derandomization: How to Find Water in the Ocean, Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization, Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma, Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds, Efficient Construction of Rigid Matrices Using an NP Oracle, Improving \(3N\) circuit complexity lower bounds, On uniformity and circuit lower bounds, Local reduction, Local expanders, Gate elimination: circuit size lower bounds and \#SAT upper bounds, Average-case rigidity lower bounds, Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression, Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly, Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs, Local Reductions