Paper list

Pick your paper below. Papers that have been claimed will be crossed out.
1. L. Valiant. General context-free recognition in less than cubic time, JCSS 1975. [pdf]
Description: Valiant shows how to use fast Boolean matrix multiplication to do context free grammar parsing.

2. L. Lee. Fast Context-Free Parsing Requires Fast Boolean Matrix Multiplication, JACM 2002. (Naveen Venkat) [pdf]
Description: Lee shows that context free grammar parsing requires Boolean matrix multiplication, i.e. that any subcubic algorithm for it implies a subcubic algorithm for BMM.

3. Amir Abboud, Arturs Backurs, V.V.Williams. If the Current Clique Algorithms are Optimal, so is Valiant's Parser, FOCS'15. [pdf]
Description: We give a new reduction to CFG parsing from k-Clique, showing that improving upon Valiant's parser even for constant size CFGs would imply new algorithms for k-Clique. This improves upon Lee's result, but making a different assumption.

4. N. Bansal, R. Williams. Regularity Lemmas and Combinatorial Algorithms. Theory of Computing 2012. (Surya Mathialagan) [pdf]
Description: Bansal and Williams show that by using graph regularity one can improve upon the Four-Russians algorithm for BMM.

5. P. Vaidya. Speeding-Up Linear Programming Using Fast Matrix Multiplication, FOCS 1989. [pdf]
Description: The author gives an algorithm for linear programming based on matrix multiplication.

6. R. Duan and S. Pettie. Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths, SODA 2009. (Yael Kirkpatrick) [pdf]
Description: The authors improve upon the first subcubic algorithm for bottleneck paths, obtaining the currently fastest algorithm for the problem.

7. T. Takaoka, Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication, CATS 2002. (Julian Viera) [pdf]
Description: The author presents an algorithm for the Max Subarray problem using APSP.

8. H. Gabow, P. Sankowski. Algebraic Algorithms for b-Matching, Shortest Undirected Paths, and f-Factors, FOCS 2013. [pdf]
Description: The authors present algorithms for shortest paths in undirected graphs with possibly negative weights, for b-matching and max flow, all based on matrix multiplication.

9. R. Yuster and U. Zwick, Fast sparse matrix multiplication, TALG 2005. (Neekon Vafa) [pdf]
Description: The authors present a fast algorithm for sparse matrix multiplication using fast dense matrix multiplication and bucketting.

10. H. Cohn, R. Kleinberg, B. Szegedy, C. Umans, Group-theoretic Algorithms for Matrix Multiplication, FOCS 2005. (Julian Wellman) [pdf]
Description: The authors propose a new approach to matrix multiplication based on finding groups with special properties.

11. N. Alon, A. Shpilka, C. Umans, On sunflowers and matrix multiplication, CCC 2012. [pdf]
Description: The authors prove interesting connections between a conjecture in combinatorics and conjectures about matrix multiplication algorithms.

12. X. Huang, V. Pan. Fast Rectangular Matrix Multiplication and Applications. J. Complexity 1998. [pdf]
Description: The authors present bounds for multiplying rectangular matrices. These bounds were not improved for several decades.

13. D. Coppersmith, Rapid Multiplication of Rectangular Matrices, SIAM J. Comput. 1982. [pdf]
Description: The author gives two proofs that there is some constant a bigger than 0.1 for which one can multiply n x n^a by n^a x n matrices in essentially optimal O~(n^2) time.

14. F. Le Gall. Faster Algorithms for Rectangular Matrix Multiplication, FOCS 2012. [pdf]
Description: The author improves upon the longstanding bounds of Huang and Pan. His improvement implies for instance that Zwick's APSP algorithm runs in O(n^{2.532}) time.

15. F. Le Gall and F. Urrutia. Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor. SODA'18. [pdf]
Description: The authors improve on the earlier paper by Le Gall and give the best known bounds for multiplying rectangular matrices.

16. M. Kowaluk, A. Lingas, E. Lundell. Counting and Detecting Small Subgraphs via Equations, SIAM J. Discrete Math. 2013. [pdf]
Description: The authors present a framework for counting small pattern subgraphs using matrix multiplication.

17. V.V.Williams, Josh Wang, Ryan Williams and Huacheng Yu. Finding Four-node subgraphs in triangle time, SODA'15. (Joshua Lee) [pdf]
Description: This paper shows how to detect any 4-node induced subgraph in the same time as finding a triangle, using matrix multiplication.

18. Mina Dalirrooyfard, Thuy Duong Vuong, Virginia Vassilevska Williams. Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles, STOC 2019. [arxiv]
Description: Follow-up on the 4-node subgraphs paper showing that all non-clique, non-independent set patterns on k=5,6 nodes can be found in the current best running time for k-1 clique. There's also some results on finding directed cycles.

19. Andreas Bjorklund, Rasmus Pagh, V.V. Williams, Uri Zwick. Listing Triangles, ICALP'14. (Edward Jin) [pdf]
Description: This paper has the current best algorithm for listing triangles in a given graph. They use matrix multiplication.

20. Greg Valiant, Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem, FOCS'12. [pdf]
Description: This paper uses matrix multiplication to find two correlated vectors that are hidden among a set of random vectors.

21. R. Yuster and U. Zwick. Finding even cycles even faster, SIAM Journal on Discrete Math, 1997. [pdf]
Description: The authors show that for any constant k>1, there is an O(n^2) time algorithm that either finds a cycle of length exactly 2k in an n-node graph, or determines no such cycle exixts. This shows that even cycles can be found faster than odd cycles, as even for just finding a triangle, the current best algorithm runs in Omega(n^{2.37}) time.

22. F. Kloks, D. Kratsch, H. Muller. Finding and counting small induced subgraphs efficiently, WG'95. [pdf]
Description: The authors give algorithms based on matrix multiplication, for finding and counting subgraphs of small size in a sparse host graph. For instance, they show that a 4-Clique can be found in O(m^{(w+1)/2}) time in a graph with m edges, where w less than 2.38 is the matrix multiplication exponent.

23. N. Alon, R. Yuster, U. Zwick. Finding and counting given length cycles, Algorithmica'97. [pdf]
Description: The authors give algorithms for finding and counting fixed length cycles in directed and undirected graphs. The running time of the algorithms depends on the length of the cycle and on the number of edges in the host graph. For instance, they show that triangles can be found in O(m^{1.41}) time. This is one of the prime papers using the high degree-low degree technique.

24. D. Dor, S. Halperin, U. Zwick, All Pairs Almost Shortest Paths, SIAM Journal on Computing'2000. [pdf]
Description: The authors present fast algorithms for approximating all pairs shortest paths (APSP) in unweighted undirected graphs. In class we showed their O~(n^{7/3}) time algorithms for a +2-approximation of APSP. The paper gives for instance an O(n^{2+2/(3k-2)}) time algorithm for +k approximation for any even constant k. They also give some bounds for spanners and emulators.

25. L. Roditty, M. Thorup, U. Zwick. Roundtrip Spanners and Roundtrip Routing in Directed Graphs, TALG'08. (Yuchong Pan) [pdf]
Description: The authors consider spanners in directed graphs. In class we showed that no nontrivial spanners can exist in directed graphs. This paper shows that if instead of approximating the distanve d(u,v) between each pair of vertices u,v, one wants to approximate d(u,v)+d(v,u), then very interesting results become possible.

26. M. Thorup, U. Zwick. Spanners and emulators with sublinear distance errors, SODA'06. [pdf]
Description: We mentioned in class that it is an open problem to obtain constant error emulators or spanners with O(n^{4/3-eps}) edges for eps\ge 0. This paper shows that one can obtain spanners and emulators with O(n^{4/3-eps}) edges, with error that depends on the distance. For instance, for any k and any undirected graph, there is a spanner with O(kn^{1+1/k}) edges and for every u,v, the estimate d'(u,v) satisfies d(u,v)\leq d'(u,v)\leq d(u,v) + O((d(u,v)^{1-1/(k-1)}).

27. M. Cygan, F. Grandoni, T. Kavitha. On pairwise spanners. STACS'13. (Victor Rong) [pdf]
Description: This paper studies spanner constructions that are only requires to approximate distances for a small subset of points (or pairs of points).

28. Greg Bodwin and V. Vassilevska Williams. Better Distance Preservers and Additive Spanners, SODA'2016. [pdf]
Description: This paper focuses on pairwise distance preservers (pairwise spanners with no error) and on additive spanner in the very sparse regime, where one desires potentially a linear number of edges, but might have to pay a polynomial additive error.

29. M. Patrascu, L. Roditty. Distance Oracles Beyond the Thorup--Zwick Bound, FOCS 2010. [pdf]
Description: This paper constitutes the first improvement over the Thorup-Zwick distance oracle presented in class. The paper shows that if one is willing to have a +1 additive error, on top of the 2-multiplicative error, then much less space can be used. The authors also extend their results for the case when the given graph is sparse.

30. M. Patrascu, L. Roditty, M. Thorup. A New Infinity of Distance Oracles for Sparse Graphs, FOCS'12. [pdf]
Description: The distance oracles of Thorup and Zwick that we presented in class only gave approximate distances for constant approximation factors. It also had the number of edges in terms of the number of vertices of the original graph. This paper gives new bounds for nonconstant approximation ratios and where the space used by the distance oracle depends on the number of edges of the original graph instead of the number of vertices.

31. A. Bernstein, D. Karger. A Nearly Optimal Oracle for Avoiding Failed Vertices and Edges, STOC'09. [pdf]
Description: This paper considers the problem of constructing distance sensitivity oracles. These are data structures that preprocess a graph and store some data, so that the following queries can be answered efficiently: given vertices u,v and a failed vertex x or edge e, return the distance between u and v in the graph excluding x or e. This paper shows how to construct such an oracle in ~mn time. The space used by the oracle is ~n^2 and the query time is constant. This is conjectured to be essentially optimal.

32. S. Chechik. Compact Routing Schemes with Improved Stretch, PODC'13. [pdf]
Description: This is the first improvement over the Thorup-Zwick compact routing scheme. The author shows how to get 3.68k-approximate paths without handshaking. In class we showed that the Thorup-Zwick scheme could get 4k-3-approximate paths without handshaking and 2k-1-approximate with handshaking.

33. C. Gavoille and C. Sommer. Sparse Spanners vs. Compact Routing. SPAA'11. [pdf]
Description: Among other nice results, this paper shows limitations on how good any compact routing scheme with additive stretch can be.

34. T. Chan, More Algorithms for All-Pairs Shortest Paths in Weighted Graphs. STOC'07 [pdf]
Description: The author gives an ~n^3/log^2 n time APSP algorithm and an algorithm for APSP in geometric graphs and graphs with node weights.

35. R. Williams. Faster all-pairs shortest paths via circuit complexity. STOC'14. [pdf]
Description: The author gives an ~n^3/2^{sqrt log n} time APSP algorithm which is the current best algorithm for the problem.

36. K. Bringmann, F. Grandoni, B. Saha and V. Vassilevska Williams. Truly Sub-cubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product. FOCS'16. [pdf]
Description: The authors present the first truly subcubic time algorithm for min-plus product for bounded difference matrices and present several applications, including to the RNA-Folding problem.

37. Shucheng Chi, Ran Duan, Tianle Xie. Faster Algorithms for Bounded-Difference Min-Plus Product. (Ziqian Zhong) [pdf]
Description: The latest subcubic algorithm for the Min-Plus product of bounded difference matrices.

38. Virginia Vassilevska Williams, Yinzhan Xu: Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications. SODA 2020 (MingYang Deng) [pdf]
Description: The most general case in which Min-Plus product can be computed in truly subcubic time.

39. R. Duan, C. Jin, H. Wu, Faster Algorithms for All Pairs Non-Decreasing Paths Problem. ICALP 2019. [pdf]
Description: The authors present the fastest algorithm for All Pairs Non-Decreasing Paths, running in ~n^{(3+omega)/2} time.

40. Josh Alman. Limits on the Universal Method for Matrix Multiplication. CCC 2019. [pdf]
Description: The author shows that even vast generalizations of the known methods for designing matrix multiplication algorithms would not be able to show that omega is less than 2.16.

41. J. van den Brand. A Deterministic Linear Program Solverin Current Matrix Multiplication Time. (Guanghao Ye) [pdf]
Description: The author presents the fastest known algorithm for linear programming, improving upon a previous randomized algorithm with the same running time.

42. Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu: Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths. ICALP 2021. [pdf]
Description: A variety of new algorithms for variants of APSP in graphs with small integer weights. Some interesting equivalences as well.

43. Yuzhou Gu, Adam Polak, Virginia Vassilevska Williams, Yinzhan Xu: Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths. [pdf]
Description: A faster algorithm for Min-Plus product for a restricted type of matrices that can then be used in applications.

44. Josh Alman, Virginia Vassilevska Williams: A Refined Laser Method and Faster Matrix Multiplication. SODA 2021. [pdf]
Description: The fastest matrix multiplication algorithm to date.

45. Jan Van den Brand. Unifying Matrix Data Structures: Simplifying and Speeding up Iterative Algorithms, SOSA 2021. (Jonathan Rodriguez Figueroa) [pdf]
Description: A new paper on a simple way to use dynamic matrix inverse to speed up some algorithms.

46. Jan van den Brand, Danupon Nanongkai, Thatchaphol Saranurak. Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds [pdf]
Description: The best algorithm to date for maintaining the inverse of a matrix dynamically.

47. Breaking the n^k Barrier for Minimum k-cut on Simple Graphs (Zhiyang He) arxiv