Efficient construction of rigid matrices using an NP oracle
From MaRDI portal
Vector spaces, linear dependence, rank, lineability (15A03) Networks and circuits as models of computation; circuit complexity (68Q06) Communication complexity, information complexity (68Q11) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites work
- A note on matrix rigidity
- A remark on matrix rigidity
- A Turing machine time hierarchy
- Almost-everywhere circuit lower bounds from non-trivial derandomization
- Average-case rigidity lower bounds
- Beating brute force for systems of polynomial equations over finite fields
- Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
- 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 polynomial evaluation and interpolation problems
- Matrix rigidity of random toeplitz matrices
- New algorithms and lower bounds for circuits with linear threshold gates
- Nonuniform ACC circuit lower bounds
- On a theorem of Razborov
- On ACC
- On the rigidity of Vandermonde matrices
- Polynomial representations of threshold functions and algorithmic applications
- PRIMES is in P
- Probabilistic polynomials and Hamming nearest neighbors
- Probabilistic rank and matrix rigidity
- Pseudodeterministic constructions in subexponential time
- Rapid Multiplication of Rectangular Matrices
- Rigid matrices from rectangular PCPs or: hard claims have complex proofs
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- 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
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 Q6930362)
