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