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: 
25.11.2013
Full text:
download
(downloads: 137)
Language: 
Russian
Heading: 
Mathematics
UDC: 
519.7
DOI: 
10.18500/1816-9791-2013-13-4-63-67

On Combinatorial Problem, Related with Fast Matrix Multiplication

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

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.

Key words: 
fast matrix multiplication
group-theoretical approach to fast matrix multiplication
USP
Cap set problem
References: 
  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):
download
(downloads: 47)
  • 771 reads