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
- Title not available (Why is that?)
- 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)
