Matrix discrepancy and the log-rank conjecture

• 成果类型: Article
• 署名作者: Sudakov, Benny; Tomon, Istvan
• 署名单位: Swiss Federal Institutes of Technology Domain; ETH Zurich; Umea University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02117-9
• 发表日期: 2025
• 页码: 567-579
• 关键词: Complexity

摘要

Given an mxn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m\times n$$\end{document} binary matrix M with |M|=pmn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|M|=p\cdot mn$$\end{document} (where |M| denotes the number of 1 entries), define the discrepancy of M as disc(M)=maxX subset of[m],Y subset of[n]||M[XxY]|-p|X||Y||\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\textrm{disc}\,}}(M)=\displaystyle \max \nolimits _{X\subset [m], Y\subset [n]}\big ||M[X\times Y]|-p|X|\cdot |Y|\big |$$\end{document}. Using semidefinite programming and spectral techniques, we prove that if rank(M)<= r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\textrm{rank}\,}}(M)\le r$$\end{document} and p <= 1/2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p\le 1/2$$\end{document}, then disc(M)>=Omega(mn)minp,p1/2r.\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned}{{\,\textrm{disc}\,}}(M)\ge \Omega (mn)\cdot \min \left\{ p,\frac{p<^>{1/2}}{\sqrt{r}}\right\} .\end{aligned}$$\end{document}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 mxn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m\times n$$\end{document} binary matrix M of rank at most r contains an (m2-O(r))x(n2-O(r))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(m\cdot 2<^>{-O(\sqrt{r})})\times (n\cdot 2<^>{-O(\sqrt{r})})$$\end{document} 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)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\sqrt{r})$$\end{document}.