Efficient Construction of Rigid Matrices Using an NP Oracle
From MaRDI portal
Cites work
- A note on matrix rigidity
- A remark on matrix rigidity
- A Turing machine time hierarchy
- Average-case rigidity lower bounds
- Beating brute force for systems of polynomial equations over finite fields
- Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
- Certifying polynomials for AC^0(parity) circuits, with applications
- Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
- Classical algorithms from quantum and Arthur-Merlin communication protocols
- Communication in bounded depth circuits
- Complexity Lower Bounds using Linear Algebra
- Counting solutions to polynomial systems via reductions
- Derandomizing Arthur-Merlin games using hitting sets
- Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Hardness vs randomness
- scientific article; zbMATH DE number 3121508 (Why is no real title available?)
- scientific article; zbMATH DE number 3597878 (Why is no real title available?)
- scientific article; zbMATH DE number 7250146 (Why is no real title available?)
- Improving exhaustive search implies superpolynomial lower bounds
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma
- Linear Circuits over $\operatorname{GF}(2)$
- Linear-time encodable and decodable error-correcting codes
- Locally decodable codes
- Lower bounds for matrix factorization
- Lower bounds for polynomial evaluation and interpolation problems
- Matrix rigidity of random toeplitz matrices
- Nonuniform ACC circuit lower bounds
- On a theorem of Razborov
- On ACC
- On the rigidity of Vandermonde matrices
- PRIMES is in P
- Probabilistic rank and matrix rigidity
- Pseudodeterministic constructions in subexponential time
- Rapid Multiplication of Rectangular Matrices
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Sampling-based dimension reduction for subspace approximation
- Short PCPs with projection queries
- Smooth and strong PCPs
- Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
- Static data structure lower bounds imply rigidity
- Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
- Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
- The landscape of communication complexity classes
- Theory and Applications of Models of Computation
- Threshold circuits of small majority-depth
- Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
- Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
- Zero-information protocols and unambiguity in Arthur-Merlin communication
Cited in
(7)- Predicate encryption from bilinear maps and one-sided probabilistic rank
- Using elimination theory to construct rigid matrices
- Matrix Rigidity from the Viewpoint of Parameterized Complexity
- Matrix Rigidity from the Viewpoint of Parameterized Complexity
- Explicit Construction of RIP Matrices Is Ramsey‐Hard
- Rigid matrices from rectangular PCPs
- Range avoidance, remote point, and hard partial truth table via satisfying-pairs algorithms
This page was built for publication: Efficient Construction of Rigid Matrices Using an NP Oracle
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5863325)
