2013/05/01 by Sarah B. Hart, Ivo Hedtke, Hart, Sarah +6
Computer Science · Engineering · #68Q17 #68Q25 #68R05 #Advanced Graph Theory Research #Coding theory and cryptography #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #FOS: Mathematics #Group Theory (math.GR) #Primary 20-04 #Secondary 20D60 #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1305.0448
openalex publication_date 2013/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a new fast search algorithm for <m,m,m> Triple Product Property\n(TPP) triples as defined by Cohn and Umans in 2003. The new algorithm achieves\na speed-up factor of 40 up to 194 in comparison to the best known search\nalgorithm. With a parallelized version of the new algorithm we are able to\nsearch for TPP triples in groups up to order 55.\n As an application we identify a list of groups that would realize 5x5 matrix\nmultiplication with under 100 resp. 125 scalar multiplications (the best known\nupper bound by Makarov 1987 resp. the trivial upper bound) if they contain a\n<5,5,5> TPP triple. With our new algorithm we show that no group can realize\n5x5 matrix multiplication better than Makarov's algorithm.\n