Fine-Grained Papers

Regular Expressions, Context-Free Grammars, and Fine-Grained Complexity
• Arturs Backurs and Piotr Indyk. Which regular expression patterns are hard to match? In FOCS 2016.[pdf]
  Description: Fine-grained 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 Backurs-Indyk result on fine-grained hardness of regular expression matching.
  
  
• 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.
  
  
• L. Lee. Fast Context-Free 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 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.
  
  
  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 Four-Russians algorithm for BMM.
  
  
• A. Czumaj and A. Lingas. Finding a Heaviest Vertex-Weighted 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 node-weighted graph in matrix-multiplication 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 Boix-Adserà, Matthew Brennan, Guy Bresler. The Average-Case Complexity of Counting Cliques in Erdos-Renyi Hypergraphs. In FOCS 2019. [pdf]
  Description: This paper presents fine-grained worst-case to average-case reductions for problems such as counting k-cliques. Unlike prior work, the reductions work also for the natural Erdos-Renyi distribution, thus showing that k-clique counting in Erdos-Renyi 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 non-induced cycles. In STOC 2019. (Yevgenii) [pdf]
  Description: This paper presents, among other things, a reduction from k-clique detection to H-induced subgraph detection for H with some natural properties.
  
  
• Kai-Yuan, Hsueh-I, Mikkel Thorup. Three-in-a-tree in near linear time. In STOC 2020. [pdf]
  Description: This paper gives the first near-linear time algorithm for the Three-in-a-tree 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 k-cliques in Sublinear Time. In STOC 2018. [pdf]
  Description: This paper has the current state-of-the art of the number of queries to a graph needed to obtain a good approximation to the number of k-cliques.
  
  
  Path Problems
• Timothy M. Chan and Ryan Williams. Deterministic APSP, (Kaarel)Orthogonal Vectors, and more: Quickly derandomizing Razborov-Smolensky. 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: Fine-grained 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 fine-grained problems equivalent to APSP: radius, median, betweenness centrality. Also some problems related to Diameter.
  
  
• Robert Krauthgamer and Ohad Trabelsi. Conditional lower bounds for all-pairs max-flow. In ICALP 2017.[pdf]
  Description: Fine-grained lower bounds for versions of max-flow.
  
  
• 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 fine-grained 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 Kisfaludi-Bak, Sudeshna Kolay. An ETH-Tight Exact Algorithm for Euclidean TSP. In FOCS 2018. [pdf]
  Description: This paper gives a 2^{O(n^{1-1/d})} time algorithm for Euclidean TSP in R^d, and a reduction showing that ETH implies that no 2^{o(n^{1-1/d})} time algorithm exists.
  
  
• Amir Abboud, Robert Krauthgamer, Ohad Trabelsi. New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs. In SODA 2020. [pdf]
  Description: This paper gives conditional lower bounds for all-pairs 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 fine-grained 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 fine-grained 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: Fine-grained 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 matrix-vector multiplication conjecture. In STOC 2015.[pdf]
  Description: This paper defines the OMV conjecture and proves a bunch of fine-grained lower bounds for dynamic problems under it.
  
  
• Kasper Green Larsen and R. Ryan Williams. Faster online matrix-vector multiplication. In SODA 2017.[pdf]
  Description: An n^3/2^{\Omega(sqrt n)} time algorithm for OMV, and more.
  
  
  Similarity Measure Problems
• Yi-Jun Chang. Hardness of RNA folding problem with four symbols. In CPM 2016. [pdf]
  Description: The author improves the prior reduction from Clique to RNA-Folding 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 fine-grained 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: Fine-grained 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: Fine-grained 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 Sub-Quadratic 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 state-of-the 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: Nearly-Linear vs Barely-Subquadratic Complexity in Computational Geometry. (Emily and Midori) In SODA 2018.[pdf]
  Description: Strong fine-grained 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.
  
  
  Sum-Related 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: Fine-grained 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 k-SUM) into unweighted ones (like k-Clique).
  
  
• Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, and R. Ryan Williams. Deterministic time-space trade-offs for k-SUM. In ICALP 2016.[pdf]
  Description: Time-space tradeoffs for k-SUM and a very believable reformulation of the 3SUM conjecture.
  
  
• Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay. SETH-Based 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^{1-eps}2^{o(n)} time algorithm for Subset Sum for any eps>0.
  
  
• Bartomiej Dudek, Pawel Gawrychowski, Tatiana Starikovskaya. All non-trivial variants of 3-LDT 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 Convolution-3SUM. In SOSA 2020.[pdf]
  Description: This paper gives a deterministic reduction from 3SUM to 3SUM-Convolution.
  
  
• Daniel Kane, Shachar Lovett, Shay Moran. Near-optimal linear decision trees for k-SUM and related problems. In STOC 2018. [pdf]
  Description: This paper gives LDTs for k-SUM of depth O(n log^2 n).
  
  
• Timothy Chan. More Logarithmic-factor Speedups for 3SUM, (median,+)-convolution, and Some Geometric 3SUM-hard Problems. In ACM TALG.[pdf]
  Description: This is the fastest algorithm for 3SUM over the reals to date.
  
  
  Fine-Grained 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 fine-grained approximation hardness for max inner product and related problems.
  
  
• Karl Bringmann, Marvin Künnemann, Karol Wegrzycki. Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max. 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 max-min 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. Fine-grained reductions from approximate counting to decision. In STOC 2018. [pdf]
  Description: This paper gives black-box fine-grained reductions from approximately counting and sampling witnesses to detection, for a class of problems including 3-SUM and 3-Clique.
  
  
• 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 black-box fine-grained 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 k-SUM, k-Clique, k-OV 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 CNF-SAT. ACM Trans. Algorithms, 2016.[pdf]
  Description: This paper gives several NP-hard problems that need 2^n time iff SAT does.
  
  
• Thomas Dueholm Hansen, Haim Kaplan, Or Zamir, Uri Zwick. Faster k-SAT algorithms using biased-PPSZ. In STOC 2019. [pdf]
  Description: Recall that the best known algorithms for k-SAT run in 2^{n(1-c/k)}poly(n) time for various constants c. This paper obtains the best constants c to-date, 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 non-reducibility. 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 non-interactive proofs of batch evaluation. In CCC 2016.[pdf]
  Description: The Nondeterministic SETH paper originally had Merlin-Arthur SETH and Arthur-Merlin SETH. Ryan disproves these here, casting doubt on NSETH.
  
  
  Fine-Grained Coding and Cryptography
• Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Average-case fine-grained hardness. In STOC 2017.[pdf]
  Description: The first results in fine-grained cryptography.
  
  
• Noah Stephens-Davidowitz, Vinod Vaikuntanathan. SETH-hardness of Coding Problems. In FOCS 2019. [pdf]
  Description: This paper gives fine-grained lower bounds based on SETH for a variety of coding problems. E.g. the paper shows that (under SETH) q^{n-o(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.
  
  
  Fine-Grained... Machine Learning???
• Arturs Backurs, Piotr Indyk, and Ludwig Schmidt. On the fine-grained complexity of empirical risk minimization: Kernel methods and neural networks. In NIPS 2017. [pdf]
  Description: Fine-grained hardness in machine learning.
  
  
• Arturs Backurs and Christos Tzamos. Improving Viterbi is hard: Better runtimes imply faster clique algorithms. In ICML 2017. [pdf]
  Description: Fine-grained 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. Fine-grained complexity of analyzing compressed data: Quantifying improvements over decompress-and-solve. In FOCS 2017. [pdf]
  Description: Fine-grained 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: Fine-grained lower bounds for model checking problems.
  
  
• Karl Bringmann, Nick Fischer, Marvin Künnemann. A Fine-Grained Analogue of Schaefer's Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order 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.