An Improved Combinatorial Algorithm for Boolean Matrix Multiplication

2015/05/26 by Yu, Huacheng · 3 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1505.06811

Abstract

We present a new combinatorial algorithm for triangle finding and Boolean matrix multiplication that runs in O(n³/log⁴ n) time, where the O notation suppresses poly(loglog) factors. This improves the previous best combinatorial algorithm by Chan that runs in O(n³/log³ n) time. Our algorithm generalizes the divide-and-conquer strategy of Chan's algorithm. Moreover, we propose a general framework for detecting triangles in graphs and computing Boolean matrix multiplication. Roughly speaking, if we can find the "easy parts" of a given instance efficiently, we can solve the whole problem faster than n³.

Cited by

• Triangle Detection in H-Free Graphs
• Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection
• (Approximate) Matrix Multiplication via Convolutions

Related

• New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
• Lower bounds for Combinatorial Algorithms for Boolean Matrix Multiplication
• A Strongly Subcubic Combinatorial Algorithm for Triangle Detection with Applications
• Faster Combinatorial k-Clique Algorithms
• Fast algorithms for anti-distance matrices as a generalization of Boolean matrices