20 citations · 164 across the 63 of their papers we have counts for
4 papers · 1 filter
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
Amir Abboud, Nick Fischer, Zander Kelley +2
We revisit the fundamental Boolean Matrix Multiplication (BMM) problem. With the invention of algebraic fast matrix multiplication over 50 years ago, it also became known that BMM…
The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues
Nikhil Bansal, Daniel Dadush, Shashwat Garg +1
An important result in discrepancy due to Banaszczyk states that for any set of vectors in of norm at most and any convex body in …
Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem
Daniel Dadush, Shashwat Garg, Shachar Lovett +1
An important theorem of Banaszczyk (Random Structures & Algorithms `98) states that for any sequence of vectors of norm at most and any convex body of Gaussian m…
Constructive Discrepancy Minimization by Walking on The Edges
Shachar Lovett, Raghu Meka
Minimizing the discrepancy of a set system is a fundamental problem in combinatorics. One of the cornerstones in this area is the celebrated six standard deviations result of Spenc…