On rank vs. communication complexity

DOI10.1007/BF01192527zbMath0845.68038OpenAlexW2175167577MaRDI QIDQ1906852

Avi Wigderson, Noam Nisan

Publication date: 15 September 1996

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01192527

zbMATH Keywords

Boolean functioncommunication complexity

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items (37)

The corruption bound, log-rank, and communication complexity ⋮ Path embeddings in faulty 3-ary \(n\)-cubes ⋮ Algebraic techniques in communication complexity ⋮ Deterministic Communication vs. Partition Number ⋮ On public-coin zero-error randomized communication complexity ⋮ The augmentation property of binary matrices for the binary and Boolean rank ⋮ Ultrametric Algorithms and Automata ⋮ Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture ⋮ Around the log-rank conjecture ⋮ Bipartite perfect matching as a real polynomial ⋮ On bounds of \(A_\alpha\)-eigenvalue multiplicity and the rank of a complex unit gain graph ⋮ Approximate nonnegative rank is equivalent to the smooth rectangle bound ⋮ Linear algebraic methods in communication complexity ⋮ Panconnectivity and edge-pancyclicity of \(k\)-ary \(n\)-cubes with faulty elements ⋮ On order and rank of graphs ⋮ Extremal problems under dimension constraints. ⋮ A counterexample to the Alon-Saks-Seymour conjecture and related problems ⋮ Unnamed Item ⋮ Some structural properties of low-rank matrices related to computational complexity ⋮ Edge-pancyclicity and path-embeddability of bijective connection graphs ⋮ Complexity measures of sign matrices ⋮ Communication complexity of some number theoretic functions ⋮ Multiparty Communication Complexity of Vector–Valued and Sum–Type Functions ⋮ Partition arguments in multiparty communication complexity ⋮ Traced communication complexity of cellular automata ⋮ Polynomial degree vs. quantum query complexity ⋮ Unnamed Item ⋮ On derandomized composition of Boolean functions ⋮ Superlinear Advantage for Exact Quantum Algorithms ⋮ On set intersection representations of graphs ⋮ Lower bounds in communication complexity based on factorization norms ⋮ An Additive Combinatorics Approach Relating Rank to Communication Complexity ⋮ Complexity measures and decision tree complexity: a survey. ⋮ Communication complexity method for measuring nondeterminism in finite automata ⋮ Evaluation of exact quantum query complexities by semidefinite programming ⋮ A Composition Theorem for Randomized Query Complexity ⋮ Upper bounds on communication in terms of approximate rank

Uses Software

• GRAFFITI

Cites Work

• Unnamed Item
• The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear
• On the distributional complexity of disjointness
• A counterexample to the rank-coloring conjecture
• A Bound for the Chromatic Number of a Graph

This page was built for publication: On rank vs. communication complexity