Document Open Access Logo

Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication

Authors Debarati Das, Michal Koucký, Michael Saks

PDF

File

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

Document Identifiers

Subject Classification

Keywords
  • Lower bounds
  • Combinatorial algorithm
  • Boolean matrix multiplication

Metrics

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

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.

Cite As Get 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

Author Details

Debarati Das
Michal Koucký
Michael Saks

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.
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