Around the log-rank conjecture

DOI10.1007/s11856-023-2517-5MaRDI QIDQ6050267

Troy Lee, Adi Shraibman

Publication date: 12 October 2023

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Boolean and Hadamard matrices (15B34) Communication complexity, information complexity (68Q11)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On conjectures of Graffiti
• A note on Ramsey numbers
• Efficient partition trees
• The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear
• On the distributional complexity of disjointness
• Communication complexity and combinatorial lattice theory
• A comparison of two lower-bound methods for communication complexity
• Geometric arguments yield better bounds for threshold circuits and distributed computing
• The corruption bound, log-rank, and communication complexity
• On rank vs. communication complexity
• On the ``log rank-conjecture in communication complexity
• Singularity of sparse Bernoulli matrices
• Ordered biclique partitions and communication complexity problems
• Exponential Lower Bounds for Polytopes in Combinatorial Optimization
• Different Modes of Communication
• Communication is Bounded by Root of Rank
• The Pattern Matrix Method
• Extensions of Lipschitz mappings into a Hilbert space
• Lower Bounds in Communication Complexity
• Perturbed Identity Matrices Have High Rank: Proof and Applications
• Learning Complexity vs Communication Complexity
• Composition Theorems in Communication Complexity
• A counterexample to the rank-coloring conjecture
• The Probabilistic Communication Complexity of Set Intersection
• A Bound for the Chromatic Number of a Graph
• Rank and chromatic number of a graph
• Deterministic Communication vs. Partition Number
• Separations in Query Complexity Based on Pointer Functions
• Communication Complexity
• The rank and size of graphs
• The Log-Approximate-Rank Conjecture Is False
• En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations
• Separations in query complexity using cheat sheets
• The approximate rank of a matrix and its algorithmic applications
• An Additive Combinatorics Approach Relating Rank to Communication Complexity
• Lower bounds in communication complexity based on factorization norms
• Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem

This page was built for publication: Around the log-rank conjecture