Regularization of low error PCPs and an application to MCSP
From MaRDI portal
Cites work
- A new PCP outer verifier with applications to homogeneous linear equations and max-bisection
- Analytical approach to parallel repetition
- Beyond natural proofs: hardness magnification and locality
- Circuit lower bounds from NP-hardness of MCSP under turing reductions
- Circuit minimization problem
- Composition of Low-Error 2-Query PCPs Using Decodable PCPs
- Constant depth formula and partial function versions of MCSP are hard
- Efficient construction of rigid matrices using an NP oracle
- Efficient probabilistically checkable proofs and applications to approximations
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- Extractors and pseudorandom generators
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Hardness magnification for natural problems
- Hardness vs randomness
- scientific article; zbMATH DE number 4179276 (Why is no real title available?)
- scientific article; zbMATH DE number 4012495 (Why is no real title available?)
- scientific article; zbMATH DE number 176876 (Why is no real title available?)
- scientific article; zbMATH DE number 3489106 (Why is no real title available?)
- scientific article; zbMATH DE number 1559537 (Why is no real title available?)
- scientific article; zbMATH DE number 7650416 (Why is no real title available?)
- Improving exhaustive search implies superpolynomial lower bounds
- Interactive proofs and the hardness of approximating cliques
- Learning algorithms from natural proofs
- Limits of minimum circuit size problem as oracle
- Multiple assignment scheme for sharing secret
- New insights on the (non-)hardness of circuit minimization and related problems
- Non-black-box worst-case to average-case reductions within NP
- NP-hardness of learning programs and partial MCSP
- On one-way functions and Kolmogorov complexity
- On the efficiency of local decoding procedures for error-correcting codes
- On the NP-Completeness of the Minimum Circuit Size Problem.
- On the range avoidance problem for circuits
- On the synthesis of self-correcting schemes from functional elements with a small number of reliable elements
- Optimization, approximation, and complexity classes
- PCP characterizations of NP: toward a polynomially-small error-probability
- Polynomially low error PCPs with \(\operatorname{polyloglog} n\) queries via modular composition
- Pseudorandomness for approximate counting and sampling
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Secret-Sharing Schemes: A Survey
- Smooth and strong PCPs
- Some optimal inapproximability results
- The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into _1
- Two-query PCP with subconstant error
- Using Nondeterminism to Amplify Hardness
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
This page was built for publication: Regularization of low error PCPs and an application to MCSP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6953178)
