Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)

For citation:

Kuznetsov Y. V. On Combinatorial Problem, Related with Fast Matrix Multiplication. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2013, vol. 13, iss. 4, pp. 63-67. DOI: 10.18500/1816-9791-2013-13-4-63-67

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
Full text:
(downloads: 135)

On Combinatorial Problem, Related with Fast Matrix Multiplication

Kuznetsov Yurii Vladimirovich, Scientific Research Institute for System Studies of RAS

The group-theoretical approach to fast matrix multiplication generates specific combinatorial objects, named Uniquely Solvable Puzzles (briefly USP). In the paper some numerical characteristic of the USP was discussed and the relation of USPs to famous combinatorial problem named «Cap set problem» was investigated.

  1. Coppersmith D., Winograd S. Matrix multiplication via arithmetic progressions. J. Symbolic Comput., 1990. Vol. 9, no. 3, pp. 251–280.
  2. Vassilevska Williams V. Multiplying Matrices Faster than Coppersmith–Winograd. Proceedings of the 44-th Symposium on Theory of Computing, STOC’12. 2012. URL: www.cs.berkeley.edu/ virgi/matrixmult.pdf (Accsessed 30, September, 2013).
  3. Cohn H., Umans C. A group theoretic approach to fast matrix multiplication. Proceedings of the 44-th Annual IEEE Symposium on Foundations of Computer Science. 2003, pp. 438–449. DOI: 10.1109/SFCS.2003.1238217.
  4. Cohn H., Kleinberg R., Szegedy B., Umans C. Group-theoretic algorithms for matrix multiplication. Proceedings of the 46-th Annual IEEE Symposium on Foundations of Computer Science. 2005, pp. 379–388. DOI: 10.1109/SFCS.2005.39.
  5. Platonov V. P., Kuznetsov Iu. V., Petrunin M. M. O teoretiko-gruppovom podkhode k probleme bystrogo umnozheniia matrits. Matematicheskoe i komp’iuternoe modelirovanie sistem: teoreticheskie i prikladnye aspekty [A group-theoretical approach to the problem of fast matrix multiplication. Mathematical and computer modeling of systems: theoretical and applied aspects]. Sbornik nauchnuh trudov NIISI RAN [Collection of scientific papers NIISI RAS]. Moscow, 2009, pp. 4–15 (in Russian).
  6. Kuznetsov Yu. V. Nekotorye kombinatornye aspekty teoretiko-gruppovogo podkhoda k probleme bystrogo umnozheniia matrits [Some combinatorial aspects of the group-theoretic approach to fast matrix multiplication]. Chebyshevskii sbornik., 2012, vol. 13, no. 1, pp. 102–109 (in Russian).
  7. Alon N., Shpilka A., Umans C. On sunflowers and matrix multiplication. Electronic Colloquium on Computational Complexity, 2011, Report no. 67, pp. 1–16.
  8. Davis B. L., Maclagan D. The card game SET. Mathematical Intelligencer, 2003, vol. 25, no. 3, pp. 33–40.
  9. Bateman M., Katz N. New bounds on caps sets. J. American Math. Soc., 2012. vol. 25, no. 2, pp. 585–613.
  10. Edel Y. Extensions of generalized product caps. Designs, Codes and Cryptography, 2004, vol. 31, pp. 5–14.
  11. Mebane P. Uniquely Solvable Puzzles and Fast Matrix Multiplication. HMC Senior Theses, 2012, 37 p.
Short text (in English):
(downloads: 46)