On a theorem of Razborov
DOI10.1007/S00037-011-0021-5zbMATH Open1279.68100OpenAlexW2048910070MaRDI QIDQ445247FDOQ445247
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) Discrete mathematics in relation to computer science (68R99) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Quasi-random graphs
- The Probabilistic Communication Complexity of Set Intersection
- Communication in bounded depth circuits
- A remark on matrix rigidity
- A note on matrix rigidity
- NP is as easy as detecting unique solutions
- Communication Complexity and Quasi Randomness
- On the rigidity of Vandermonde matrices
- Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
- A linear lower bound on the unbounded error probabilistic communication complexity.
- Matrix rigidity
- PP is as Hard as the Polynomial-Time Hierarchy
- Complexity Lower Bounds using Linear Algebra
- Lower Bounds on Matrix Rigidity Via a Quantum Argument
- Theory and Applications of Models of Computation
- Some structural properties of low-rank matrices related to computational complexity
- A new upper bound for the bipartite Ramsey problem
- On the distributional complexity of disjointness
- Probabilistic complexity classes and lowness
- Learning Complexity vs Communication Complexity
- Lower bounds in communication complexity based on factorization norms
- Halfspace matrices
- Sparse quasi-random graphs
- Complexity and structure
- On counting problems and the polynomial-time hierarchy
- Some combinatorial-algebraic problems from complexity theory
- Noise-resilient group testing: limitations and constructions
- On relations between counting communication complexity classes
- Average and randomized communication complexity
- On Toda’s Theorem in Structural Communication Complexity
- Computational Complexity of Cast Puzzles
- Counting classes: Thresholds, parity, mods, and fewness
- On the complexity of topological sorting
Cited In (11)
- Rabinowitz's theorems revisited
- Limits of preprocessing
- Efficient Construction of Rigid Matrices Using an NP Oracle
- Title not available (Why is that?)
- The landscape of communication complexity classes
- On a theorem of I.I.Privalov
- Zero-information protocols and unambiguity in Arthur-Merlin communication
- Rigid matrices from rectangular PCPs
- A note on a theorem of Rantzer
- On a theorem of Rigby
- Title not available (Why is that?)
This page was built for publication: On a theorem of Razborov
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q445247)
