Bounds for Combinatorial Algorithms in Boolean Matrix Multiplication
Explore lower bounds for combinatorial algorithms in Boolean matrix multiplication, discussing techniques, methodologies, and results from joint research work. Understand the importance of combinatorial algorithms and their applications.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication Michal Kouck Charles University Joint work with: Debarati Das and Mike Saks
Boolean Matrix Multiplication (BMM) 0 ?1,? 1 ?2,? 1 ?3,? 1 ??,? 1 0 1 1 0 0 1 0 ??,? 1 0 1 0 1 0 1 0 0 1 ??,1??,2 ??,? 1 0 1 0 . = 0 1 Multiplication over Boolean semi-ring: ? ??,?= ?=1 (??,? ??,?)
Boolean Matrix Multiplication (BMM) ? ? = ? ? ? ? ? ? ? ? ?
Algorithms for BMM ?(?3) na ve Fast matrix multiplication: ?(?2.373) [Strassen 69, Coppersmith-Winograd 90, Vassilevska Williams 12, Le Gall 14] Combinatorial algorithms: ?(?3/log2 ?) ?(?3/log2.25 ?) ?(?3/log3 ?) ?(?3/log4 ?) [Arlazarov-Dinic-Kronrod-Faradzhev 70] [Bansal-Williams 12] [Chan 15] [Yu 15]
Combinatorial algorithms Not based on Fast Matrix Multiplication. Derive information in monotone fashion. produce witness/proof for the matrix product proof system
Why combinatorial algorithms? Easier to understand and implement. Provide intuition for multiplication over other semi-rings: (min, +)-semi-ring All Pairs Shortest Paths ?3 log ?[Williams] best alg.: O 2O
Angluins model (1976) = 1 0 1 1 ? ? ? Each resulting row union of rows of ?.
Angluins model (1976) ? Circuit of row unions from ?, might depend on both ? and ?. Question: How many unions in total? Angluin: ?(?2/log?).
Angluins model (1976) Question: How many unions in total? Angluin: (?2/log?) by counting argument. ? If cost of each union is ?(?), total time ?(?3/log ?). On a random instance, each row is all 1 s after ? log? unions ? ?log? distinct unions.
Our model #1 Angluin s circuits. Charge only for distinct (content) unions. Cost of a union number of 1 s in the smaller vector. ? finger-printing + sparse vector representation On a random instance, each row is all 1 s after ? log? unions total cost ? ?2log? .
Our result #1 Angluin s circuits. Charge only for distinct (content) unions. Cost of a union number of 1 s in the smaller vector. ? ?3 log ?. Thm: Cost of BMM in our model is at least 2O
Our model #2 ? Cost: ?(1) 1. Break rows into continuous pieces. 2. Concatenate pieces. 3. Take union of pieces. ? 1 min. # of 1 s.
Our result #2 3. Concatenate pieces. 2. Union pieces. ? 1. Break rows. ? ?2+1/3 log ?. Thm: Cost of BMM in our model #2 is at least 2O Can implement the Four Russians Algorithm .
Generalized model 1. Break rows into continuous pieces. 2. Concatenate pieces. 3. Take union of pieces. ? ? Question 1: What s the cost when one mixes the operations in arbitrary order? Question 2: What s the right choice of cost function?
Hard graphs Rusza-Szemer di (1978): There exists a bipartite graph on 2? vertices which is a union of ?/3 disjoint induced matchings each of size ?/2?( log ?). ? ?
Hard graphs Rusza-Szemer di (1978): There exists a bipartite graph on 2? vertices which is a union of ?/3 disjoint induced matchings each of size ?/2?( log ?). matchings ? ? ?
Hard graphs Dense graph with ?2/2?( log ?) pairs of vertices which are connected via a unique path. matchings ? ? ?
Open problems The right model of combinatorial algorithms? New combinatorial algorithms? Lower bounds on combinatorial algorithms?
