Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication

Authors Debarati Das, Michal Koucký, Michael Saks



PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.23.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Debarati Das
Michal Koucký
Michael Saks

Cite AsGet BibTex

Debarati Das, Michal Koucký, and Michael Saks. Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.STACS.2018.23

Abstract

In this paper we propose models of combinatorial algorithms for the Boolean Matrix Multiplication (BMM), and prove lower bounds on computing BMM in these models. First, we give a relatively relaxed combinatorial model which is an extension of the model by Angluin (1976), and we prove that the time required by any algorithm for the BMM is at least Omega(n^3 / 2^{O( sqrt{ log n })}). Subsequently, we propose a more general model capable of simulating the "Four Russian Algorithm". We prove a lower bound of Omega(n^{7/3} / 2^{O(sqrt{ log n })}) for the BMM under this model. We use a special class of graphs, called (r,t)-graphs, originally discovered by Rusza and Szemeredi (1978), along with randomization, to construct matrices that are hard instances for our combinatorial models.
Keywords
  • Lower bounds
  • Combinatorial algorithm
  • Boolean matrix multiplication

Metrics

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

References

  1. Noga Alon, Ankur Moitra, and Benny Sudakov. Nearly complete graphs decomposable into large induced matchings and their applications. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 1079-1090. ACM, 2012. URL: http://dx.doi.org/10.1145/2213977.2214074.
  2. Dana Angluin. The four russians' algorithm for boolean matrix multiplication is optimal in its class. In ACM SIGACT News, pages 19-33, 1976. Google Scholar
  3. Nikhil Bansal and Ryan Williams. Regularity lemmas and combinatorial algorithms. Theory of Computing, 8(1):69-94, 2012. URL: http://dx.doi.org/10.4086/toc.2012.v008a004.
  4. Timothy M. Chan. Speeding up the four russians algorithm by about one more logarithmic factor. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 212-217. SIAM, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.16.
  5. Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. J. Symb. Comput., 9(3):251-280, 1990. URL: http://dx.doi.org/10.1016/S0747-7171(08)80013-2.
  6. Michael J Fischer and Albert R Meyer. Boolean matrix multiplication and transitive closure. In 12th Annual Symposium on Switching and Automata Theory, pages 129-131, 1971. Google Scholar
  7. M. E. Furman. Application of a method of fast multiplication of matrices in the problem of finding the transitive closure of a graph. Soviet Mathematics Doklady, page 11(5):1252, 1970. Google Scholar
  8. François Le Gall. Powers of tensors and fast matrix multiplication. In Katsusuke Nabeshima, Kosaku Nagasaka, Franz Winkler, and Ágnes Szántó, editors, International Symposium on Symbolic and Algebraic Computation, ISSAC '14, Kobe, Japan, July 23-25, 2014, pages 296-303. ACM, 2014. URL: http://dx.doi.org/10.1145/2608628.2608664.
  9. Alon Itai. Finding a minimum circuit in a graph. In John E. Hopcroft, Emily P. Friedman, and Michael A. Harrison, editors, Proceedings of the 9th Annual ACM Symposium on Theory of Computing, May 4-6, 1977, Boulder, Colorado, USA, pages 1-10. ACM, 1977. URL: http://dx.doi.org/10.1145/800105.803390.
  10. Ian Munro. Efficient determination of the transitive closure of a directed graph. Information Processing Letters, pages 1(2):56–-58, 1971. Google Scholar
  11. I. Ruszá and E. Szemerédi. Triple systems with no six points carrying three triangles. In Colloquia Mathematica Societatis János Bolyai, pages 939-945, 1978. Google Scholar
  12. V. Strassen. Gaussian elimination is not optimal. In Numer. Math, pages 13:354–-356, 1969. Google Scholar
  13. M. A. Kronrod V. Z. Arlazarov, E. A. Dinic. On economical construction of the transitive closure of a directed graph. Soviet Mathematics Doklady, pages 11(5):1209–-1210, 1970. Google Scholar
  14. Leslie G. Valiant. General context-free recognition in less than cubic time. Journal of computer and system sciences, pages 10(2):308–-315, 1975. Google Scholar
  15. Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 887-898. ACM, 2012. URL: http://dx.doi.org/10.1145/2213977.2214056.
  16. Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle problems. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 645-654. IEEE Computer Society, 2010. URL: http://dx.doi.org/10.1109/FOCS.2010.67.
  17. Huacheng Yu. An improved combinatorial algorithm for boolean matrix multiplication. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 1094-1105. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_89.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail