Short PCPs with projection queries

DOI10.1007/978-3-662-43948-7_14MaRDI QIDQ5167739zbMATH OpenOpenAlexFDO

Authors Eli Ben-Sasson, Emanuele Viola

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

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

Recommendations

• Constant rate PCPs for circuit-SAT with sublinear query complexity
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Derandomized parallel repetition via structured PCPs
• More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
• Short PCPs with Polylog Query Complexity

Cited in

(25)

• 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
• Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
• Quasi-linear size zero knowledge from linear-algebraic PCPs
• Local reductions
• Towards hardness of approximation for polynomial time problems
• On uniformity and circuit lower bounds
• Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
• Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds
• 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
• scientific article; zbMATH DE number 7250146 (Why is no real title available?)
• Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma
• Efficient Construction of Rigid Matrices Using an NP Oracle
• Small PCPs with low query complexity
• Improving \(3N\) circuit complexity lower bounds
• Rigid matrices from rectangular PCPs
• Towards stronger depth lower bounds
• Efficient construction of rigid matrices using an NP oracle
• Nondeterministic quasi-polynomial time is average-case hard for \textsf{ACC} circuits

This page was built for publication: Short PCPs with projection queries

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