Document Open Access Logo

On the Binary and Boolean Rank of Regular Matrices

Authors Ishay Haviv, Michal Parnas

PDF

File

Thumbnail PDF
PDF
LIPIcs.MFCS.2022.56.pdf
  • Filesize: 0.62 MB
  • 14 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Communication complexity
  • Mathematics of computing → Graph coloring
Keywords
  • Binary rank
  • Boolean rank
  • Regular matrices
  • Non-deterministic communication complexity
  • Biclique partition number
  • Chromatic number

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

A 0,1 matrix is said to be regular if all of its rows and columns have the same number of ones. We prove that for infinitely many integers k, there exists a square regular 0,1 matrix with binary rank k, such that the Boolean rank of its complement is k^Ω̃(log k). Equivalently, the ones in the matrix can be partitioned into k combinatorial rectangles, whereas the number of rectangles needed for any cover of its zeros is k^Ω̃(log k). This settles, in a strong form, a question of Pullman (Linear Algebra Appl., 1988) and a conjecture of Hefner, Henson, Lundgren, and Maybee (Congr. Numer., 1990). The result can be viewed as a regular analogue of a recent result of Balodis, Ben-David, Göös, Jain, and Kothari (FOCS, 2021), motivated by the clique vs. independent set problem in communication complexity and by the (disproved) Alon-Saks-Seymour conjecture in graph theory. As an application of the produced regular matrices, we obtain regular counterexamples to the Alon-Saks-Seymour conjecture and prove that for infinitely many integers k, there exists a regular graph with biclique partition number k and chromatic number k^Ω̃(log k).

Cite As Get BibTex

Ishay Haviv and Michal Parnas. On the Binary and Boolean Rank of Regular Matrices. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.MFCS.2022.56

Author Details

Ishay Haviv
  • The Academic College of Tel Aviv-Yaffo, Tel Aviv, Israel
Michal Parnas
  • The Academic College of Tel Aviv-Yaffo, Tel Aviv, Israel

Funding

  • Haviv, Ishay: Research supported in part by the Israel Science Foundation (grant No. 1218/20).

Acknowledgements

We thank the anonymous reviewers for their helpful and constructive comments.

References

  1. Kazuyuki Amano. Some improved bounds on communication complexity via new decomposition of cliques. Discret. Appl. Math., 166:249-254, 2014. Google Scholar
  2. Kaspars Balodis, Shalev Ben-David, Mika Göös, Siddhartha Jain, and Robin Kothari. Unambiguous DNFs and Alon-Saks-Seymour. In IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS'21), pages 116-124. IEEE, 2021. Google Scholar
  3. Shalev Ben-David, Pooya Hatami, and Avishay Tal. Low-sensitivity functions from unambiguous certificates. In 8th Innovations in Theoretical Computer Science Conference (ITCS'17), pages 28:1-28:23, 2017. Google Scholar
  4. Jan Bouda, Matej Pivoluska, and Martin Plesch. Improving the Hadamard extractor. Theor. Comput. Sci., 459:69-76, 2012. Google Scholar
  5. Nicolas Bousquet, Aurélie Lagoutte, Frédéric Maffray, and Lucas Pastor. Decomposition techniques applied to the clique-stable set separation problem. Discret. Math., 341(5):1492-1501, 2018. Google Scholar
  6. Nicolas Bousquet, Aurélie Lagoutte, and Stéphan Thomassé. Clique versus independent set. European J. Combinatorics, 40:73-92, 2014. Google Scholar
  7. Richard A. Brualdi, Rachel Manber, and Jeffrey A. Ross. On the minimum rank of regular classes of matrices of zeros and ones. J. Combin. Theory Ser. A, 41(1):32-49, 1986. Google Scholar
  8. Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, and Toniann Pitassi. Query-to-communication lifting using low-discrepancy gadgets. SIAM J. Comput., 50(1):171-210, 2021. Preliminary version in ICALP'19. Google Scholar
  9. Benny Chor and Oded Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J. Comput., 17(2):230-261, 1988. Preliminary version in FOCS'85. Google Scholar
  10. Maria Chudnovsky and Paul Seymour. Subdivided claws and the clique-stable set separation property. In 2019-20 MATRIX Annals, volume 4, pages 483-487. Springer, 2021. Google Scholar
  11. Sebastian M. Cioabă and Michael Tait. More counterexamples to the Alon-Saks-Seymour and rank-coloring conjectures. Electron. J. Combinatorics, 18(1), 2011. Google Scholar
  12. D. de Caen, David A. Gregory, and Norman J. Pullman. The Boolean rank of zero-one matrices. Proc. of the 3rd Caribbean Conference on Combinatorics and Computing, pages 169-173, 1981. Google Scholar
  13. Mika Göös. Lower bounds for clique vs. independent set. In IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS'15), pages 1066-1076, 2015. Google Scholar
  14. Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman. Rectangles are nonnegative juntas. SIAM J. Comput., 45(5):1835-1869, 2016. Preliminary version in STOC'15. Google Scholar
  15. Mika Göös, Toniann Pitassi, and Thomas Watson. Deterministic communication vs. partition number. SIAM J. Comput., 47(6):2435-2450, 2018. Preliminary version in FOCS'15. Google Scholar
  16. Ronald L. Graham and Henry O. Pollak. On the addressing problem for loop switching. Bell Syst. Tech. J., 50(8):2495-2519, 1971. Google Scholar
  17. David A. Gregory, Norman J. Pullman, Kathryn F. Jones, and J. Richard Lundgren. Biclique coverings of regular bigraphs and minimum semiring ranks of regular matrices. J. Comb. Theory, Ser. B, 51(1):73-89, 1991. Google Scholar
  18. Kim A. S. Hefner, Teresa D. Henson, J. Richard Lundgren, and John S. Maybee. Biclique coverings of bigraphs and digraphs and minimum semiring ranks of 0,1-matrices. Congr. Numer., 71:115-122, 1990. Google Scholar
  19. Hao Huang and Benny Sudakov. A counterexample to the Alon-Saks-Seymour conjecture and related problems. Combinatorica, 32(2):205-219, 2012. Google Scholar
  20. Stasys Jukna. Boolean Function Complexity - Advances and Frontiers, volume 27 of Algorithms and Combinatorics. Springer, 2012. Google Scholar
  21. Jeff Kahn. Recent results on some not-so-recent hypergraph matching and covering problems. In Extremal Problems for Finite Sets, pages 305-353. Bolyai Soc. Math. Stud., 1994. Google Scholar
  22. Pravesh K. Kothari, Raghu Meka, and Prasad Raghavendra. Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. In Proc. of the 49th Annual ACM Symposium on Theory of Computing (STOC'17), pages 590-603, 2017. Google Scholar
  23. Aurélie Lagoutte and Théophile Trunck. Clique-stable set separation in perfect graphs with no balanced skew-partitions. Discret. Math., 339(6):1809-1825, 2016. Google Scholar
  24. László Lovász and Michael E. Saks. Lattices, Möbius functions and communication complexity. In IEEE 29th Annual Symposium on Foundations of Computer Science (FOCS'88), pages 81-90, 1988. Google Scholar
  25. Shachar Lovett. Recent advances on the log-rank conjecture in communication complexity. Bull. EATCS, 112, 2014. Google Scholar
  26. Sylvia D. Monson, Norman J. Pullman, and Rolf Rees. A survey of clique and biclique coverings and factorizations of (0,1)-matrices. Bull. Inst. Combin. Appl., 14:17-86, 1995. Google Scholar
  27. Norman J. Pullman. Ranks of binary matrices with constant line sums. Linear Algebra Appl., 104:193-197, 1988. Google Scholar
  28. Alexander A. Razborov. The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear. Discret. Math., 108(1-3):393-396, 1992. Google Scholar
  29. Manami Shigeta and Kazuyuki Amano. Ordered biclique partitions and communication complexity problems. Discret. Appl. Math., 184:248-252, 2015. Google Scholar
  30. Mihalis Yannakakis. Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci., 43(3):441-466, 1991. Preliminary version in STOC'88. Google Scholar
  31. Andrew Chi-Chih Yao. Some complexity questions related to distributive computing. In Proc. of the 11th Annual ACM Symposium on Theory of Computing (STOC'79), pages 209-213, 1979. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact