Short PCPs with Projection Queries
From MaRDI portal
Publication:5167739
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
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