On a theorem of Razborov

DOI10.1007/S00037-011-0021-5MaRDI QIDQ445247zbMATH OpenOpenAlexFDO

Authors Henning Wunderlich

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

zbMATH Keywords

communication complexitystructural complexitymatrix rigidityquasi-random graphapproximate ranktheorem of RazborovToda's theorems

Mathematics Subject Classification ID

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)

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

(11)

• A note on a theorem of Rantzer
• Zero-information protocols and unambiguity in Arthur-Merlin communication
• On a theorem of I.I.Privalov
• Limits of preprocessing
• Rigid matrices from rectangular PCPs
• The landscape of communication complexity classes
• Efficient Construction of Rigid Matrices Using an NP Oracle
• scientific article; zbMATH DE number 7561745 (Why is no real title available?)
• On a theorem of Rigby
• Rabinowitz's theorems revisited
• scientific article; zbMATH DE number 4010916 (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)