On a theorem of Razborov
From MaRDI portal
Publication:445247
DOI10.1007/s00037-011-0021-5zbMath1279.68100OpenAlexW2048910070MaRDI QIDQ445247
Publication date: 24 August 2012
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-011-0021-5
communication complexitystructural complexitymatrix rigidityquasi-random graphapproximate ranktheorem of RazborovToda's theorems
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Discrete mathematics in relation to computer science (68R99)
Related Items
The landscape of communication complexity classes ⋮ Zero-information protocols and unambiguity in Arthur-Merlin communication ⋮ Unnamed Item ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A remark on matrix rigidity
- A note on matrix rigidity
- On the complexity of topological sorting
- Halfspace matrices
- Complexity and structure
- NP is as easy as detecting unique solutions
- On counting problems and the polynomial-time hierarchy
- On the distributional complexity of disjointness
- Probabilistic complexity classes and lowness
- Communication in bounded depth circuits
- Some combinatorial-algebraic problems from complexity theory
- On the rigidity of Vandermonde matrices
- Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
- Noise-resilient group testing: limitations and constructions
- Sparse quasi-random graphs
- A linear lower bound on the unbounded error probabilistic communication complexity.
- On relations between counting communication complexity classes
- Matrix rigidity
- Some structural properties of low-rank matrices related to computational complexity
- PP is as Hard as the Polynomial-Time Hierarchy
- Complexity Lower Bounds using Linear Algebra
- Average and randomized communication complexity
- Learning Complexity vs Communication Complexity
- On Toda’s Theorem in Structural Communication Complexity
- Lower Bounds on Matrix Rigidity Via a Quantum Argument
- A new upper bound for the bipartite Ramsey problem
- Computational Complexity of Cast Puzzles
- The Probabilistic Communication Complexity of Set Intersection
- Communication Complexity and Quasi Randomness
- Quasi-random graphs
- Theory and Applications of Models of Computation
- Lower bounds in communication complexity based on factorization norms
- Counting classes: Thresholds, parity, mods, and fewness
