Efficient Construction of Rigid Matrices Using an NP Oracle

DOI10.1137/20M1322297OpenAlexW4220805816MaRDI QIDQ5863325

Lijie Chen, Josh Alman

Publication date: 11 March 2022

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

Full work available at URL: https://doi.org/10.1137/20m1322297

zbMATH Keywords

PCP of proximitymatrix rigiditycircuit lower boundsprobabilistically checkable proof

Mathematics Subject Classification ID

Related Items (1)

Predicate encryption from bilinear maps and one-sided probabilistic rank

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A remark on matrix rigidity
• Zero-information protocols and unambiguity in Arthur-Merlin communication
• On a theorem of Razborov
• A Turing machine time hierarchy
• A note on matrix rigidity
• Derandomizing Arthur-Merlin games using hitting sets
• Threshold circuits of small majority-depth
• Communication in bounded depth circuits
• Hardness vs randomness
• On ACC
• Lower bounds for polynomial evaluation and interpolation problems
• On the rigidity of Vandermonde matrices
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
• The landscape of communication complexity classes
• Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
• PRIMES is in P
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Smooth and strong PCPs
• Lower bounds for matrix factorization
• Average-case rigidity lower bounds
• Improving Exhaustive Search Implies Superpolynomial Lower Bounds
• Certifying polynomials for AC^0(parity) circuits, with applications
• Linear-time encodable and decodable error-correcting codes
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• Nonuniform ACC Circuit Lower Bounds
• Complexity Lower Bounds using Linear Algebra
• Linear Circuits over $\operatorname{GF}(2)$
• Sampling-based dimension reduction for subspace approximation
• Rapid Multiplication of Rectangular Matrices
• Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
• Beating Brute Force for Systems of Polynomial Equations over Finite Fields
• New algorithms and lower bounds for circuits with linear threshold gates
• Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
• Probabilistic rank and matrix rigidity
• Pseudodeterministic constructions in subexponential time
• Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
• Short PCPs with Projection Queries
• Static data structure lower bounds imply rigidity
• Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
• Counting Solutions to Polynomial Systems via Reductions
• Matrix rigidity of random toeplitz matrices
• Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
• Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Locally Decodable Codes
• Theory and Applications of Models of Computation
• Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma

This page was built for publication: Efficient Construction of Rigid Matrices Using an NP Oracle