On the ``log rank-conjecture in communication complexity

DOI10.1007/BF01192528zbMath0845.68050OpenAlexW2174446922WikidataQ122964261 ScholiaQ122964261MaRDI QIDQ1906853

Boris Spieker, Ran Raz

Publication date: 15 September 1996

Published in: Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

communication complexity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

The corruption bound, log-rank, and communication complexity, Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices, Algebraic techniques in communication complexity, Around the log-rank conjecture, A counterexample to the Alon-Saks-Seymour conjecture and related problems, Partition arguments in multiparty communication complexity, Lower bounds for the majority communication complexity of various graph accessibility problems, On set intersection representations of graphs, Testing properties of functions on finite groups, Chromatic number and the 2-rank of a graph, Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth

Cites Work

• Unnamed Item
• The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear
• Communication complexity and combinatorial lattice theory
• A counterexample to the rank-coloring conjecture
• Whitney Number Inequalities for Geometric Lattices