Rigid matrices from rectangular PCPs

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

Cites Work

Unnamed Item
Unnamed Item
A remark on matrix rigidity
On a theorem of Razborov
On uniformity and circuit lower bounds
A Turing machine time hierarchy
A note on matrix rigidity
Short propositional formulas represent nondeterministic computations
Self-testing/correcting with applications to numerical problems
Matrix rigidity of random Toeplitz matrices
In search of an easy witness: Exponential time vs. probabilistic polynomial time.
Smooth and strong PCPs
Average-case rigidity lower bounds
Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
Natural Proofs versus Derandomization
Universal Factor Graphs
Improving Exhaustive Search Implies Superpolynomial Lower Bounds
A Sample of Samplers: A Computational Perspective on Sampling
Linear-time encodable and decodable error-correcting codes
Proof verification and the hardness of approximation problems
Nonuniform ACC Circuit Lower Bounds
On the efficiency of local decoding procedures for error-correcting codes
Complexity Lower Bounds using Linear Algebra
Locally testable codes and PCPs of almost-linear length
Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
Sub-Constant Error Low Degree Test of Almost-Linear Size
Short PCPs with Polylog Query Complexity
Universal Arguments and their Applications
Probabilistic checking of proofs
Simple Constructions of Almost k-wise Independent Random Variables
Relations Among Complexity Measures
Probabilistic rank and matrix rigidity
Deterministic APSP, Orthogonal Vectors, and More
Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
Short PCPs with Projection Queries
Matrix rigidity and the Croot-Lev-Pach lemma
Computational Complexity
Composition of Low-Error 2-Query PCPs Using Decodable PCPs
Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
Fourier and Circulant Matrices are Not Rigid
Efficient Construction of Rigid Matrices Using an NP Oracle
The PCP theorem by gap amplification
Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma

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