FineGrained Papers
Pick a paper (or a group of papers) below. Papers that have been claimed will be crossed out.
You can also propose to study a paper (or group of papers) that are not on this list, or you can propose a project not in any paper!
Regular Expressions, ContextFree Grammars, and FineGrained Complexity
 Arturs Backurs and Piotr Indyk. Which regular expression patterns are hard to match? In FOCS 2016.[pdf]
Description: Finegrained hardness for regular expressions, based on OV.
 Karl Bringmann, Allan Grønlund, and Kasper Green Larsen. A dichotomy for regular expression
membership testing. In FOCS
2017.[pdf]
Description:
A generalization of the original BackursIndyk result on finegrained hardness of regular expression matching.

L. Valiant. General contextfree 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.

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

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 kClique, showing that improving upon Valiant's parser even for constant size CFGs would imply new algorithms for kClique. This improves upon Lee's result, but making a different assumption.
Finding Subgraphs and Matrix Multiplication

N. Bansal, R. Williams. Regularity Lemmas and Combinatorial Algorithms. Theory of Computing 2012.
[pdf]
Description: Bansal and Williams show that by using graph regularity one can improve upon the FourRussians algorithm for BMM.
 A. Czumaj and A. Lingas. Finding a Heaviest VertexWeighted Triangle Is not Harder than Matrix Multiplication. SIAM J. Comput. 2009.
[pdf]
Description: The authors show how one can find a min weight triangle in a nodeweighted graph in matrixmultiplication time.
 Huacheng Yu. An improved combinatorial algorithm for boolean matrix multiplication. In ICALP 2015.[pdf]
Description: This is the fastest ``combinatorial'' algorithm for BMM to date.
 Enric BoixAdserà, Matthew Brennan, Guy Bresler.
The AverageCase Complexity of Counting Cliques in ErdosRenyi Hypergraphs. In FOCS 2019.
[pdf]
Description: This paper presents finegrained worstcase to averagecase reductions for problems such as counting kcliques. Unlike prior work, the reductions work also for the natural ErdosRenyi distribution, thus showing that kclique counting in ErdosRenyi random graphs is as hard as counting cliques in arbitrary graphs.

Virginia Vassilevska Williams, Yinzhan Xu.
Monochromatic Triangles, Triangle Listing and APSP. In FOCS 2020.
[pdf]
Description: This paper shows, among other things, that the Exact Triangle problem can be reduced to listing triangles, and hence the latter problem is at least as hard as 3SUM and APSP.
Mina Dalirrooyfard, Thuy Duong Vuong, Virginia Vassilevska Williams.
Graph pattern detection: hardness for all induced patterns and faster noninduced cycles. In STOC 2019. (Yevgenii)
[pdf]
Description: This paper presents, among other things, a reduction from kclique detection to Hinduced subgraph detection for H with some natural properties.

KaiYuan, HsuehI, Mikkel Thorup. Threeinatree in near linear time. In STOC 2020.
[pdf]
Description: This paper gives the first nearlinear time algorithm for the Threeinatree problem which asks if a given undirected graph contains an induced subgraph that is a tree connecting three given vertices. The problem has many applications. The previous best algorithm had a polynomial, but much higher than linear running time.
 Talya Eden, Dana Ron, C. Seshadhri. On Approximating the Number of kcliques in Sublinear Time. In STOC 2018.
[pdf]
Description: This paper has the current stateofthe art of the number of queries to a graph needed to obtain a good approximation to the number of kcliques.
Path Problems
 Timothy M. Chan and Ryan Williams. Deterministic APSP, (Kaarel)Orthogonal Vectors, and more: Quickly
derandomizing RazborovSmolensky. In SODA 2016.[pdf]
Description: The authors derandomize Ryan's APSP algorithm, OV algorithm, and more.
 Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Or Zamir.
Subtree isomorphism revisited. In SODA 2016.
[pdf]
Description: Finegrained lower bounds for subtree isomorphism.
 Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between
graph centrality problems, APSP and diameter. In SODA 2015.[pdf]
Description:
More finegrained problems equivalent to APSP: radius, median, betweenness centrality. Also some problems related to Diameter.
 Robert Krauthgamer and Ohad Trabelsi. Conditional lower bounds for allpairs maxflow. In ICALP 2017.[pdf]
Description: Finegrained lower bounds for versions of maxflow.
 Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. Tight hardness for shortest
cycles and paths in sparse graphs. In SODA 2018.[pdf]
Description: APSP in sparse graphs needs mn time, unless there are better weighted Clique algorithms, and other finegrained results.

Jesper Nederlof.
Bipartite TSP in O(1.9999^n) Time, Assuming Quadratic Time Matrix Multiplication. In STOC 2020.
[pdf]
Description: This paper shows that if nxn matrices can be multiplied in n^{2+o(1)} time, as is often conjectured, then there is a truly faster than 2^n time algorithm for the Traveling Salesperson Problem in bipartite graphs, improving the longstanding dynamic programming algorithm running time of Held and Karp.
 Mark de Berg, Hans L. Bodlaender, Sándor KisfaludiBak, Sudeshna Kolay.
An ETHTight Exact Algorithm for Euclidean TSP. In FOCS 2018. [pdf]
Description: This paper gives a 2^{O(n^{11/d})} time algorithm for Euclidean TSP in R^d, and a reduction showing that ETH implies that no 2^{o(n^{11/d})} time algorithm exists.

Amir Abboud, Robert Krauthgamer, Ohad Trabelsi.
New Algorithms and Lower Bounds for AllPairs MaxFlow in Undirected Graphs. In SODA 2020. [pdf]
Description: This paper gives conditional lower bounds for allpairs max flow and also some new algorithms.
Dynamic/Online Algorithms
 Søren Dahlgaard. On the hardness of partially dynamic graph problems and connections to diameter.
In ICALP 2016.[pdf]
Description:
This paper considers incremental and decremental dynamic algorithms and shows finegrained hardness for them.
 Amir Abboud and Søren Dahlgaard. Popular conjectures as a barrier for dynamic planar graph algorithms.
In FOCS 2016.
[pdf]
Description: The authors present finegrained lower bounds for problems in planar graphs.
 Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3sum conjecture. In SODA
2016.[pdf]
Description:
As the title says, higher lowed bounds for dynamic problems, under 3SUM.
 Monika Henzinger, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska Williams. Conditional
hardness for sensitivity problems. In ITCS 2017.[pdf]
Description: Finegrained lower bounds for sensitivity problems  these are a more restricted variant of dynamic problems.
 Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying
and strengthening hardness for dynamic problems via the online matrixvector multiplication
conjecture. In STOC 2015.[pdf]
Description: This paper defines the OMV conjecture and proves a bunch of finegrained lower bounds for dynamic problems under it.
 Kasper Green Larsen and R. Ryan Williams. Faster online matrixvector multiplication. In SODA 2017.[pdf]
Description: An n^3/2^{\Omega(sqrt n)} time algorithm for OMV, and more.
Similarity Measure Problems
 YiJun Chang. Hardness of RNA folding problem with four symbols. In CPM 2016. [pdf]
Description:
The author improves the prior reduction from Clique to RNAFolding to show that the problem is hard even on the alphabet {A,C,U,G}.
 Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time
(unless SETH is false). In STOC 2015.
[pdf]
Description: This paper gives the first finegrained hardness for Edit Distance.

Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams. Simulating
branching programs with edit distance and friends: or: a polylog shaved is a lower bound
made. In STOC 2016.
[pdf]
Description: The authors give much stronger lower bounds for sequence similarity problems.
 Amihood Amir, Timothy M. Chan, Moshe Lewenstein, and Noa Lewenstein. On hardness of jumbled indexing. In ICALP 2014.
[pdf]
Description: Conditional hardness for the jumbled indexing problem.

Karl Bringmann, Pawel Gawrychowski, Shay Mozes, and Oren Weimann. Tree edit distance cannot
be computed in strongly subcubic time (unless APSP can). CoRR, abs/1703.08940, 2017.
[pdf]
Description:
Finegrained hardness for tree edit distance based on Clique and APSP.
 Karl Bringmann. Why walking the dog takes time: Frechet distance has no strongly subquadratic
algorithms unless SETH fails. In FOCS 2014. [pdf]
Description:
Finegrained hardness for Frechet distance, based on OV.
 Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks.
Approximating Edit Distance within Constant Factor in Truly SubQuadratic Time. In FOCS 2018. [pdf]
Description: This paper gives the first constant factor approximation algorithm for Edit Distance that runs in truly subquadratic time.
 Mahdi Boroujeni, Masoud Seddighin, Saeed Seddighin.
Improved Algorithms for Edit Distance and Longest Common Subsequence. In SODA 2020.
[pdf]
Description: This paper gives truly subquadratic 1+o(1) approximation algorithms for Edit Distance and LCS for certain structured inputs, where one string is randomly perturbed, and the second string is adversarily chosen. The current stateofthe art approximation in truly subquadratic time for these two problems is very far from 1+o(1).
Orthogonal Vectors and Nearest Neighbor Problems
 Josh Alman and Ryan Williams. Probabilistic polynomials and Hamming nearest neighbors. In FOCS 2015.
[pdf]
Description:
The authors give slightly improved algorithms for Hamming nearest neighbors and other problems using the polynomial method. You've seen some of this in class.

Ryan Williams. On the Difference Between Closest, Furthest, and Orthogonal Pairs: NearlyLinear vs BarelySubquadratic Complexity in Computational Geometry. (Emily and Midori) In SODA 2018.[pdf]
Description: Strong finegrained hardness for geometric problems based on OV.
 Ryan Williams and Huacheng Yu. Finding orthogonal vectors in discrete structures. In SODA 2014.[pdf]
Description: OV is easy over finite fields, and more results.

Lijie Chen and Ryan Williams. An Equivalence Class for Orthogonal Vectors. SODA 2019. (Emily and Midori)[pdf]
Description: This paper proves several interesting equivalences surrounding OV.
SumRelated Problems
 Jeff Erickson. Lower bounds for linear satisfiability problems. In SODA 1995.[pdf]
Description: The paper gives a quadratic lower bound for 3SUM in the linear decision tree model with width 3.
 A. Gajentaan and M. Overmars. On a class of O(n^2) problems in computational geometry. Computational
Geometry, 1995.[pdf]
Description: The original 3SUM lower bounds paper.
 Arturs Backurs, Nishanth Dikkala, and Christos Tzamos. Tight hardness results for maximum weight rectangles. In ICALP
2016.
[pdf]
Description: Finegrained hardness for the maximum subarray problem and related problems.

Amir Abboud, Kevin Lewi, and Ryan Williams. Losing weight by gaining edges. In ESA 2014. [pdf]
Description: The authors give techniques for transforming weighted problems (like kSUM) into unweighted ones (like kClique).
 Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, and R. Ryan Williams. Deterministic timespace tradeoffs for kSUM. In ICALP 2016.[pdf]
Description:
Timespace tradeoffs for kSUM and a very believable reformulation of the 3SUM conjecture.

Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay.
SETHBased Lower Bounds for Subset Sum and Bicriteria Path. In SODA 2019.
[pdf]
Description: This paper considers the Subset Sum problem with n input numbers and target T. There is a pseudopolynomial time algorithm that runs in T*poly(n) time, and the main result of this paper is that SETH implies that there can be no T^{1eps}2^{o(n)} time algorithm for Subset Sum for any eps>0.
Bartomiej Dudek, Pawel Gawrychowski, Tatiana Starikovskaya.
All nontrivial variants of 3LDT are equivalent. In STOC 2020. (Kaarel)
[pdf]
Description: This paper shows an equivalence between 3SUM and problems parameterized by integers w_1,w_2,w_3 and T and asking whether a given set of integers contains three a,b,c so that w_1*a+w_2*b+2_3*c=T.
 Timothy Chan and Qijeng He. Reducing 3SUM to Convolution3SUM. In SOSA 2020.[pdf]
Description: This paper gives a deterministic reduction from 3SUM to 3SUMConvolution.
 Daniel Kane, Shachar Lovett, Shay Moran.
Nearoptimal linear decision trees for kSUM and related problems. In STOC 2018.
[pdf]
Description: This paper gives LDTs for kSUM of depth O(n log^2 n).
 Timothy Chan. More Logarithmicfactor Speedups for 3SUM, (median,+)convolution, and Some Geometric 3SUMhard Problems. In ACM TALG.[pdf]
Description: This is the fastest algorithm for 3SUM over the reals to date.
FineGrained Approximation

Amir Abboud, Aviad Rubinstein, and R. Ryan Williams. Distributed PCP theorems for hardness of approximation in P. In FOCS 2017.
[pdf]
Description: The authors give very strong finegrained approximation hardness for max inner product and related problems.
 Karl Bringmann, Marvin Künnemann, Karol Wegrzycki.
Approximating APSP without scaling: equivalence of approximate minplus and exact minmax. In STOC 2019. [pdf]
Description: Zwick'02 showed that APSP in directed graphs with nonnegative integer weights bounded by W has an (1+eps)approximation algorithm running in time ~n^\omega / eps * log(W/eps) time. This paper shows that if one does not allow a log(W) dependence on the running time, approximate APSP becomes equivalent to the maxmin product of matrices. The fastest running time for the latter problem has a much higher, n^{(3+omega)/2} running time than Zwick's algorithm (when W is small enough, e.g. poly(n)).

Holger Dell, John Lapinskas.
Finegrained reductions from approximate counting to decision. In STOC 2018. [pdf]
Description: This paper gives blackbox finegrained reductions from approximately counting and sampling witnesses to detection, for a class of problems including 3SUM and 3Clique.
 Holger Dell, John Lapinskas, Kitty Meeks.
Approximately counting and sampling small witnesses using a colourful decision oracle. In SODA 2020.
[pdf]
Description: This paper extends the blackbox finegrained reductions of Dell and Lapinskas'2018 for arbitrary k, showing how to reduce approximately counting and sampling witnesses to detection, for a large class of problems including kSUM, kClique, kOV etc.
CNF SAT and Various Exponential Time Hypotheses
 Marek Cygan, Holger Dell, Daniel Lokshtanov, Daniel Marx, Jesper Nederlof, Yoshio Okamoto,
Ramamohan Paturi, Saket Saurabh, and Magnus Wahlstr¨om. On problems as hard as CNFSAT. ACM
Trans. Algorithms, 2016.[pdf]
Description:
This paper gives several NPhard problems that need 2^n time iff SAT does.

Thomas Dueholm Hansen, Haim Kaplan, Or Zamir, Uri Zwick. Faster kSAT algorithms using biasedPPSZ. In STOC 2019. [pdf]
Description: Recall that the best known algorithms for kSAT run in 2^{n(1c/k)}poly(n) time for various constants c. This paper obtains the best constants c todate, with a variant of the PPSZ algorithm.
 Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan
Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences
for nonreducibility. In ITCS 2016.[pdf]
Description: The authors define a nondeterministic version of NSETH and show that under it, one cannot reduce OV to 3SUM or APSP deterministically.
 Richard Ryan Williams. Strong ETH breaks with Merlin and Arthur: Short noninteractive proofs of
batch evaluation. In CCC 2016.[pdf]
Description: The Nondeterministic SETH paper originally had MerlinArthur SETH and ArthurMerlin SETH. Ryan disproves these here, casting doubt on NSETH.
FineGrained Coding and Cryptography
 Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Averagecase finegrained
hardness. In STOC 2017.[pdf]
Description: The first results in finegrained cryptography.
 Noah StephensDavidowitz, Vinod Vaikuntanathan.
SETHhardness of Coding Problems. In FOCS 2019. [pdf]
Description: This paper gives finegrained lower bounds based on SETH for a variety of coding problems. E.g. the paper shows that (under SETH) q^{no(n)} time is needed to compute for a given target t and a linear code C with q^n codewords, the minimum over all codewords x in C, of the Hamming distance between x and t.
FineGrained... Machine Learning???
 Arturs Backurs, Piotr Indyk, and Ludwig Schmidt. On the finegrained complexity of empirical risk
minimization: Kernel methods and neural networks. In NIPS 2017.
[pdf]
Description:
Finegrained hardness in machine learning.
 Arturs Backurs and Christos Tzamos. Improving Viterbi is hard: Better runtimes imply faster clique
algorithms. In ICML 2017.
[pdf]
Description:
Finegrained hardness for the Viterbi problem, based on a conjecture for the complexity of Clique.
Other
 Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching triangles and basing hardness on an extremely popular conjecture. In STOC 2015.
[pdf]
Description: The authors give two problems that are harder than SAT, 3SUM and APSP.
 Amir Abboud, Arturs Backurs, Karl Bringmann, and Marvin Kunnemann. Finegrained complexity of analyzing compressed data: Quantifying improvements over decompressandsolve. In FOCS 2017.
[pdf]
Description: Finegrained lower bounds for problems on compressed instances.
 Krishnendu Chatterjee, Wolfgang Dvor´ak, Monika Henzinger, and Veronika Loitzenbauer. Model
and objective separation with conditional lower bounds: Disjunction is harder than conjunction. In LICS ’16. [pdf]
Description: Finegrained lower bounds for model checking problems.
 Karl Bringmann, Nick Fischer, Marvin Künnemann.
A FineGrained Analogue of Schaefer's Theorem in P: Dichotomy of Exists^kForallQuantified FirstOrder Graph Properties. In CCC 2019.
[pdf]
 Rasmus Kyng, Di Wang, Peng Zhang.
Packing LPs are Hard to Solve Accurately, Assuming Linear Equations are Hard. In SODA 2020.
[pdf]
Description: As the title suggests, this paper presents a reduction from solving systems of linear equations accurately to solving "Packing" Linear Programs accurately.