Matrix discrepancy and the log-rank conjecture

2023/11/30 by Benny Sudakov, Sudakov, Benny, István Tomon +1 · 2 citations
Engineering · Computer Science · #graph theory and CDMA systems #Complexity and Algorithms in Graphs

paper · pdf · doi:10.48550/arxiv.2311.18524

Abstract

Given an m× n binary matrix M with |M|=p⋅ mn (where |M| denotes the number of 1 entries), define the discrepancy of M as disc(M)=max_{X⊂ [m], Y⊂ [n]}||M[X× Y]|-p|X|⋅ |Y||. Using semidefinite programming and spectral techniques, we prove that if rank(M)≤ r and p≤ 1/2, then disc(M)≥ Ω(mn)⋅ min\p,\fracp^1/2√(r)\. We use this result to obtain a modest improvement of Lovett's best known upper bound on the log-rank conjecture. We prove that any m× n binary matrix M of rank at most r contains an (m⋅ 2^-O(√(r)))× (n⋅ 2^-O(√(r))) sized all-1 or all-0 submatrix, which implies that the deterministic communication complexity of any Boolean function of rank r is at most O(√(r)).

Cited by

• A note on matchings and co-matchings in bipartite graphs
• The Log-Rank Conjecture: New Equivalent Formulations

Related

• A direct proof for Lovett's bound on the communication complexity of low rank matrices
• An additive combinatorics approach to the log-rank conjecture in\n communication complexity
• A Note on the LogRank Conjecture in Communication Complexity
• The Log-Rank Conjecture: New Equivalent Formulations
• Communication is bounded by root of rank