Communication is bounded by root of rank

2013/06/08 by Lovett, Shachar · 3 citations
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1306.1877

Abstract

We prove that any total boolean function of rank r can be computed by a deterministic communication protocol of complexity O(√(r) ⋅ log(r)). Equivalently, any graph whose adjacency matrix has rank r has chromatic number at most 2^{O(√(r) ⋅ log(r))}. This gives a nearly quadratic improvement in the dependence on the rank over previous results.

Cited by

• A note on matchings and co-matchings in bipartite graphs
• The Log-Rank Conjecture: New Equivalent Formulations
• A Hierarchy for Constant Communication Complexity

Related

• A direct proof for Lovett's bound on the communication complexity of low rank matrices
• A Note on the LogRank Conjecture in Communication Complexity
• The Corruption Bound, Log Rank, and Communication Complexity
• Structure in Communication Complexity and Constant-Cost Complexity Classes
• Log-rank and lifting for AND-functions