Recommendations
- Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
- Some combinatorial-algebraic problems from complexity theory
- Probabilistic rank and matrix rigidity
- The ``log rank conjecture for modular communication complexity
- Lower Bounds on Matrix Rigidity Via a Quantum Argument
Cites work
- scientific article; zbMATH DE number 3597878 (Why is no real title available?)
- scientific article; zbMATH DE number 1072530 (Why is no real title available?)
- scientific article; zbMATH DE number 1361464 (Why is no real title available?)
- A linear lower bound on the unbounded error probabilistic communication complexity.
- A new upper bound for the bipartite Ramsey problem
- A note on matrix rigidity
- A remark on matrix rigidity
- Average and randomized communication complexity
- Communication Complexity and Quasi Randomness
- Communication in bounded depth circuits
- Complexity Lower Bounds using Linear Algebra
- Complexity and structure
- Computational complexity of cast puzzles
- Counting classes: Thresholds, parity, mods, and fewness
- Halfspace matrices
- Learning complexity vs communication complexity
- Lower Bounds on Matrix Rigidity Via a Quantum Argument
- Lower bounds in communication complexity based on factorization norms
- Matrix rigidity
- NP is as easy as detecting unique solutions
- Noise-resilient group testing: limitations and constructions
- On Toda’s Theorem in Structural Communication Complexity
- On counting problems and the polynomial-time hierarchy
- On relations between counting communication complexity classes
- On the complexity of topological sorting
- On the distributional complexity of disjointness
- On the rigidity of Vandermonde matrices
- PP is as Hard as the Polynomial-Time Hierarchy
- Probabilistic complexity classes and lowness
- Quasi-random graphs
- Some combinatorial-algebraic problems from complexity theory
- Some structural properties of low-rank matrices related to computational complexity
- Sparse quasi-random graphs
- Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
- The Probabilistic Communication Complexity of Set Intersection
- Theory and Applications of Models of Computation
Cited in
(13)- Rabinowitz's theorems revisited
- Limits of preprocessing
- Efficient Construction of Rigid Matrices Using an NP Oracle
- scientific article; zbMATH DE number 4010916 (Why is no real title available?)
- The landscape of communication complexity classes
- Block rigidity: strong multiplayer parallel repetition implies super-linear lower bounds for Turing machines
- 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
- Efficient construction of rigid matrices using an NP oracle
- scientific article; zbMATH DE number 7561745 (Why is no real title available?)
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)
