Rigid matrices from rectangular PCPs

DOI10.1137/22M1495597MaRDI QIDQ6491304zbMATH OpenFDO

Authors Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal

Publication date 24 April 2024

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/22M1495597

zbMATH Keywords

complexity theorymatrix rigidityprobabilistically checkable proofs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites work

• scientific article; zbMATH DE number 3597878 (Why is no real title available?)
• A Turing machine time hierarchy
• A note on matrix rigidity
• A remark on matrix rigidity
• A sample of samplers: a computational perspective on sampling
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• Average-case rigidity lower bounds
• Complexity Lower Bounds using Linear Algebra
• Composition of low-error 2-query PCPs using decodable PCPs
• Computational Complexity
• Deterministic APSP, Orthogonal Vectors, and More
• Efficient Construction of Rigid Matrices Using an NP Oracle
• Fourier and circulant matrices are not rigid
• Improving exhaustive search implies superpolynomial lower bounds
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Inapproximability of combinatorial optimization problems
• Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma
• Linear-time encodable and decodable error-correcting codes
• Locally testable codes and PCPs of almost-linear length
• Matrix rigidity and the Croot-Lev-Pach lemma
• Matrix rigidity of random Toeplitz matrices
• Nonuniform ACC circuit lower bounds
• On a theorem of Razborov
• On the efficiency of local decoding procedures for error-correcting codes
• On uniformity and circuit lower bounds
• Probabilistic checking of proofs
• Probabilistic rank and matrix rigidity
• Proof verification and the hardness of approximation problems
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
• Relations Among Complexity Measures
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Self-testing/correcting with applications to numerical problems
• Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
• Short PCPs with Polylog Query Complexity
• Short PCPs with projection queries
• Short propositional formulas represent nondeterministic computations
• Simple Constructions of Almost k-wise Independent Random Variables
• Smooth and strong PCPs
• Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
• Sub-Constant Error Low Degree Test of Almost-Linear Size
• The PCP theorem by gap amplification
• Universal Arguments and their Applications
• Universal factor graphs

This page was built for publication: Rigid matrices from rectangular PCPs

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