Short PCPs with Projection Queries

DOI10.1007/978-3-662-43948-7_14zbMath1410.68135OpenAlexW184142732MaRDI 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

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (20)

On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection ⋮ Local Reductions ⋮ Local reduction ⋮ Quantified Derandomization: How to Find Water in the Ocean ⋮ Local expanders ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ Unnamed Item ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ 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 ⋮ New algorithms and lower bounds for circuits with linear threshold gates ⋮ On uniformity and circuit lower bounds ⋮ Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs ⋮ Unnamed Item ⋮ 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 ⋮ Unnamed Item ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle ⋮ Average-case rigidity lower bounds

This page was built for publication: Short PCPs with Projection Queries