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 Gronlund, 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. (Avi) [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. (Avi Balsam) [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 previous fastest ``combinatorial'' algorithm for BMM until 2024.
  
  
• Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka: New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms. In STOC 2024. (Shuo)[pdf]
  Description: This is the fastest "combinatorial" algorithm to date. It shaves all polylogs from n^3.
  
  
• 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. We saw a much simplified reduction in class.
  
  
• Mina Dalirrooyfard, Thuy Duong Vuong, Virginia Vassilevska Williams. Graph pattern detection: hardness for all induced patterns and faster non-induced cycles. In STOC 2019. [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.
  
  
• Mina Dalirrooyfard, Surya Mathialagan, Virginia Vassilevska Williams, Yinzhan Xu: Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques. In STOC 2024 [pdf]
  Description: This paper presents algorithms for listing k-cliques in a graph, where the running time depends on both the input and the output size, i.e. the number of k-cliques. Fine-grained lower bounds give conditional hardness in some regimes.
  
  
• 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.
  
  
• Amir Abboud, Shon Feller, Oren Weimann. On the Fine-Grained Complexity of Parity Problems. In ICALP 2020. [pdf]
  Description: This paper shows that some problems are fine-grained equivalent to a natural parity variant.
  
  
• 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.
  
  
• Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu. Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV. In STOC 2022. [pdf]
  Description: This paper gives a reduction to the All-Edge Sparse Triangles (equivalent to the triangle listing problem that we saw in class) from the versions of 3SUM and APSP on real numbered instances. Other interesting reductions as well.
  
  
  Path Problems
• Timothy M. Chan and Ryan Williams. Deterministic APSP, 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. (Michal Stawarz) [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, Sandor Kisfaludi-Bak, Sudeshna Kolay. An ETH-Tight Exact Algorithm for Euclidean TSP. In FOCS 2018. (Michal Stawarz) [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.
  
  
• Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, Ohad Trabelsi. Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time. In FOCS 2022. [pdf]
  Description: This paper gives an almost optimal algorithm for All-Pairs Max-Flow.
  
  
• Amir Abboud, Vincent Cohen-Addad, Philip N. Klein. New hardness results for planar graph problems in P and an algorithm for sparsest cut. In STOC 2020. [pdf]
  Description: This paper gives conditional lower bounds for natural problems in planar graphs.
  
  
• Andrea Lincoln, Adam Polak, Virginia Vassilevska Williams. Monochromatic Triangles, Intermediate Matrix Products, and Convolutions. In ITCS 2020:. [pdf]
  Description: This paper gives equivalences and reductions between several "intermediate" problems: either matrix products with running times around n^{2.5} (if omega=2), or convolution problems with running times ~n^{1.5}.
  
  
• Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu. Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths. In ICALP 2021. [pdf]
  Description: This paper proves ~n^{2.5} time equivalences between unweighted directed APSP and other shortest paths problems, following up on the above paper by Lincoln, Polak and VW.
  
  
• Yuzhou Gu, Adam Polak, Virginia Vassilevska Williams, Yinzhan Xu. Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths. ICALP 2021. [pdf]
  Description: This paper gives algorithms and conditional lower bounds for Single Source Replacement Paths in graphs with possibly negative edge weights and for a few other problems.
  
  
• Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu: Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More. In STOC 2023. [pdf]
  Description: This paper gives a powerful method for fine-grained reductions using matrix multiplication. A sample theorem shows that Counting the number of 3SUM solutions is equivalent to detecting a 3SUM solution.
  
  
• Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu: Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths. In ICALP 2021.[pdf]
  Description: This paper gives several equivalences between small weight variants of the APSP problem. For instance it shows that the unweighted directed APSP problem is equivalent to a rectangular (n by sqrt n by n) version of Min-Plus product for matrices with weights bounded by sqrt n.
  
  
  Dynamic/Online Algorithms
• Soren Dahlgaard. On the hardness of partially dynamic graph problems and connections to diameter. In ICALP 2016. (Eugeniya)[pdf]
  Description: This paper considers incremental and decremental dynamic algorithms and shows fine-grained hardness for them.
  
  
• Amir Abboud and Soren Dahlgaard. Popular conjectures as a barrier for dynamic planar graph algorithms. In FOCS 2016. (Eugeniya) [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.
  
  
• Hung Le, Lazar Milenkovic, Shay Solomon, Virginia Vassilevska Williams. Dynamic Matching Algorithms Under Vertex Updates. In ITCS 2022.[pdf]
  Description: The paper considers the dynamic matching problem under vertex insertions and deletions. A conditional lower bound from the Omv problem (and triangle detection) is given for certain restricted types of algorithms.
  
  
  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). (Fares) 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). In SODA 2018. [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 Koucky, 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).
  
  
• Amir Abboud, Virginia Vassilevska Williams. Fine-Grained Hardness for Edit Distance to a Fixed Sequence. In ICALP 2021. [pdf]
  Description: This remarkably simple paper shows that problems like Edit Distance are still SETH-hard when one of the input sequences is fixed and only depends on the input length n.
  
  
  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. 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. (Zixiang Zhou)[pdf]
  Description: OV is easy over finite fields, and more results.
  
  
• Lijie Chen and Ryan Williams. An Equivalence Class for Orthogonal Vectors. SODA 2019. [pdf]
  Description: This paper proves several interesting equivalences surrounding OV.
  
  
• Lijie Chen. On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product. Theory Comput. [pdf]
  Description: This paper proves OV based hardness for Maximum Inner Product.
  
  
• Ryan Williams: The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds. In FOCS 2024. [pdf]
  Description: This paper gives a new approach towards refuting the OV conjecture. Along the way it proves win-win circuit lower bounds.
  
  
  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. [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.
  
  
• Daniel Kane, Shachar Lovett, Shay Moran. Near-optimal linear decision trees for k-SUM and related problems. (Anton) In STOC 2018, JACM 2019. [pdf].
  Description: This paper gives LDTs for k-SUM of depth O(n log^2 n). Similarly almost-optimal LDTs are shown (if you stare hard enough) for APSP.
  
  
• 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. Also has some log improvements for some geometry problems.
  
  
  Fine-Grained Approximation
• Amir Abboud, Aviad Rubinstein, and R. Ryan Williams. Distributed PCP theorems for hardness of approximation in P. In FOCS 2017. Kshitij [pdf]
  Description: The authors give very strong fine-grained approximation hardness for max inner product and related problems.
  
  
• Karl Bringmann, Marvin Kunnemann, 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.
  
  
• Amir Abboud, Karl Bringmann, Seri Khoury, Or Zamir. Hardness of approximation in P via short cycle removal: cycle detection, distance oracles, and beyond. In STOC 2022. [pdf]
  Description: This paper gives conditional lower bounds for distance oracles and path and cycle problems. For instance, it introduces a technique to remove 4-cycles in a medium-degree graph so that triangle detection is somewhat hard in 4-cycle-free graphs.
  
  
• Amir Abboud, Karl Bringmann, Nick Fischer: Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics. In STOC 2023.[pdf]
  Description: This paper gives even stronger conditional lower bounds for distance oracles and path and cycle problems, improving upon the paper above. An independent paper with similar results is below.
  
  
• Ce Jin, Yinzhan Xu: Removing Additive Structure in 3SUM-Based Reductions. In STOC 2023. [pdf]
  Description: This paper gives even stronger conditional lower bounds for distance oracles and path and cycle problems, improving upon the paper 2 bullets above. An independent paper with similar results is right above.
  
  
• Mina Dalirrooyfard, Ray Li, Virginia Vassilevska Williams: Hardness of Approximate Diameter: Now for Undirected Graphs. In FOCS 2021. [pdf]
  Description: This paper gives SETH-based hardness, an approximation/running time tradeoff for the graph diameter problem. It shows for instance that the simple linear time 2-approximation for diameter that follows from the triangle inequality is optimal, assuming SETH.
  
  
  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 Wahlstrom. 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.
  
  
• Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, Ryan Williams. Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity. In ITCS 2022. [pdf]
  Description: This is a follow-up to Ryan's Merlin-Arthur SETH paper, giving surprisingly good Merlin-Arthur protocols for central fine-grained problems such as APSP, k-Clique, QBF and more.
  
  
• Nikhil Vyas, Ryan Williams. Results on a Super Strong Exponential Time Hypothesis. In AAAI 2020, [pdf]
  Description: The paper explores the Super Strong ETH that stipulates that the "correct" running time for k-SAT is roughly 2^{n-O(n/k)}. The paper shows that Super Strong ETH is false for random formulas. It also shows that the version of Super SETH in which the formula has a unique satisfying assignment or is unsatisfiable is equivalent to Super SETH.
  
  
  Fine-Grained Coding, Cryptography and Worst-Case to Average-Case Reductions
• 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.
  
  
• Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar. Worst-case to average-case reductions via additive combinatorics. In STOC 2022. Dingding [pdf]
  Description: This paper gives a highly nontrivial worst-case to average-case reduction for matrix multiplication.
  
  
• Oded Goldreich, Guy N. Rothblum. Counting t-cliques: Worst-case to average-case reductions and Direct interactive proof systems. ECCC. (Andrew Huang) [pdf]
  Description: This paper proves worst-case to average-case reductions for counting k-cliques.
  
  
• 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 follows up on the Goldreich-Rothblum paper above. It 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.
  
  
• Mina Dalirrooyfard, Andrea Lincoln, Virginia Vassilevska Williams: New Techniques for Proving Fine-Grained Average-Case Hardness. In FOCS 2020. [pdf]
  Description: This paper gives new worst-case to average-case reductions for variants of OV, k-SUM and more.
  
  
  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. (Jason Yang) [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.
  
  
• Josh Alman, Yunfeng Guan: Finer-Grained Hardness of Kernel Density Estimation. In CCC 2024. [pdf]
  Description: This paper improves the earlier work on fine-grained hardness for kernel density estimation under SETH.
  
  
  Other
• Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching triangles and basing hardness on an extremely popular conjecture. In STOC 2015. (Marco Rodriguez) [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.