Research projects

SETH-Based Lower Bounds for Subset Sum and Bicriteria Path 

Summary: While trying to prove a SETH lower bound for the classical Bicriteria Path problem (essentially "Knapsack on graphs"), we discovered a tight reduction from k-SAT to Subset Sum! Improving the O*(T) algorithm of Bellman from 1962 to O(T^0.99) refutes SETH.
Near-Optimal Compression for the Planar Graph Metric 

Summary: How much can you compress a planar graph without losing the ability to recover the exact distance between any pair of nodes among a certain subset of the nodes? Somehow, this basic question about one of the most extensively studied metrics remained open. We find the optimal answer, up to log factors. 
        Towards Hardness of Approximation for Polynomial Time Problems 

        Summary: One of the biggest open questions in Fine-Grained complexity is to prove that one cannot approximate LCS and Edit-Distance to within (1+eps) in near-linear time. No one has any idea how to prove such results. We present a framework for proving such "hardness of approximation" results, if we restrict the algorithms to be deterministic. In particular, we show that a deterministic (1+eps) approximation for LCS over large alphabets implies a breakthrough in Circuit Complexity.
          A Hierarchy of Lower Bounds for Sublinear Additive Spanners.

          Summary: Say we want to compress or sparsify graphs down to n^{1+1/k} edges. How much error in the distances should we suffer? Our previous work showed that distances must increase from d to beyond d+f(k), but what about d+f(d,k) as in "sublinear spanners"? We prove lower bounds on the possible functions f(d,k), giving an almost complete answer to these questions.
            Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks.

            Summary: Consider a communication model where in every round, each node gets to send a message of length O(log n) to each one of its neighbors. How many rounds are needed in order to compute a basic property of the network, such as the diameter? We show a tight near-linear lower bound on the number of rounds. This is the first lower bound higher than sqrt(n) that applies to sparse graphs. 
              • A. Abboud, Søren Dahlgaard  [arxiv[video]  FOCS 2016.
              Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms.

              Summary: We prove the first "Hardness in P" results for problems on planar graphs. For example, we show that dynamic planar APSP requires polynomial update or query times, under the (standard) APSP conjecture.

              Simulating Branching Programs with Edit Distance and Friends
                      Or: A Polylog Shaved is a Lower Bound Made

              Summary: We prove that Edit Distance and LCS are even harder than what recent works have discovered: They can solve SAT not only on CNF formulas (as in SETH lower bounds), but also SAT on very large circuits, branching programs, and turing machines. One striking consequence of our work is that even shaving a few log factors over the n^2 bound for these problems would imply major advances in circuit complexity.

                The 4/3 Additive Spanner Exponent is Tight.

                Summary: Graphs cannot be sparsified to n^4/3-eps edges, not even compressed into n^4/3-eps bits (!), while preserving the distances up to constant additive error.
                Error Amplification for Pairwise Spanner Lower Bounds. SODA 2016.
                Summary: We prove new lower bounds for "Pairwise Spanners" by presenting (denser-than-before) constructions of graphs in which the removal of a constant number of edges will necessarily increase a pairwise distance between a pair of nodes from a small set of pairs. Our constructions use an "error amplification" trick which uses a special kind of graph product. 
                Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs. SODA 2016. 
                Summary: This paper contains many things: (1) we introduce the "Hitting Set Conjecture" and show its consequences for quadratic time problems, (2) we introduce the new concept of searching for "fixed parameter subquadratic" algorithms for problems with natural parameters that cannot be solved in subquadratic time in general, (3) we devise new approximation and F.P.Subquadratic algorithms for radius and diameter. A cool result is that Diameter can be solved in 2^O(k log k)*n^{1.1} time, where k is the treewidth of the input graph, but cannot be solved in 2^o(k)*n^1.9 under SETH.
                Subtree Isomorphism Revisited. SODA 2016 (invited to special issue).
                Summary: Given two rooted binary trees on O(n) nodes - how fast can we check if one is a subtree of the other? We show that in general there is a tight n^{2-o(1)} SETH lower bound, and we present a truly subquadratic randomized algorithm for the case of low depth trees. 

                If the Current Clique Algorithms are Optimal, so is Valiant's Parser. FOCS 2015 (invited to special issue), Berkeley, CA. [slides[video] [pdf]
                Summary: k-Clique is reduced to recognizing a context-free language. Under the plausible conjecture that Clique algorithms are optimal, we prove: Valiant's seminal parsing algorithm from 1975 is optimal, and there are no "efficient" subcubic algorithms for parsing, RNA folding, and Dyck Edit Distance.
                Quadratic-Time Hardness of LCS and other Sequence Similarity Measures. FOCS 2015. [pdf]
                Summary: One of the simplest problems is: what is the longest common subsequence of two strings? We show that the classic quadratic-time dynamic programming algorithm is essentially optimal, under SETH! Tight lower bounds are given for other interesting similarity measures as well.
                            Matching Triangles and Basing Hardness on an Extremely Popular Conjecture.  STOC 2015 (invited to special issue), Portland, OR. [slides] [pdf]
                SummaryThe extremely plausible hypothesis that at least one of the three popular conjectures (3SUM, APSP, and SETH) is true, is shown to imply a tight subcubic lower bound for an innocent looking triangle finding problem we call Matching Triangles. By further reductions, we obtain interesting lower bounds for other problems like ST-Max-Flow and dynamic reachability. Moreover, the parameterized version of Matching Triangles turns out to reveal a hierarchy of natural graph problems with complexity between n^2 and n^3.
                Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter.  SODA 2015, San Diego, CA. [slides] [pdf]
                Summary: Computing the Radius, Median and Betweenness Centrality in graphs can be solved in truly subcubic time iff APSP can! i.e. we add three new problems to the APSP subcubic equivalence class. Related problems turn out to be subcubic equivalent to Diameter.
                  More Applications of the Polynomial Method to Algorithm Design.  SODA 2015 [pdf]
                  Summary: New algorithms are provided for many problems including CNF-SAT and Longest Common Substring with don't cares, by first reducing to Orthogonal Vectors, and then solving Orthogonal Vectors using the technique introduced by Williams (STOC 14') in his faster APSP algorithm.

                  Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems.  FOCS 2014, Philadelphia, PA. [slides] [video[pdf]
                  Summary: The trivial algorithms for many fundamental dynamic data-structures problems are essentially optimal, unless certain popular conjectures about classic static problems, like SETH, are false. The (long) list of problems includes reachability, strongly connected components and matching.
                  (mentioned in Eppstein's blog)
                      Losing Weight by Gaining Edges.  ESA 2014, Wroclaw, Poland. [slides[pdf]
                      Summary: k-SUM on n numbers can be reduced to k-Clique on roughly n nodes. Moreover, node-weighted versions of Clique and Dominating-Set are not (polynomially) harder than the unweighted versions! One interesting consequence is that k-SUM is (essentially) W[1]-complete. 
                      (mentioned in Lipton's blog)
                              Consequences of Faster Alignment of Sequences.  ICALP 2014, Copenhagen, Denmark. [slides[pdf]
                              Summary: We provide strong theoretical evidence that Local Alignment cannot be solved in truly subquadratic time: such algorithm would refute SETH (a breakthrough in satisfiability algorithm), the 3-SUM conjecture (from computational geometry), and give a very surprising algorithm for Min-4-Clique.  
                              (mentioned in Aceto's blog)

                              •  Hardness for Easy Problems.  YR-ICALP 2014, Copenhagen, Denmark. [slides(A 20-minute survey on the recent attempts to classify the poly-time problems)


                              Exact Weight Subgraphs and the k-SUM Conjecture.  ICALP 2013, Riga, Latvia. [slides[pdf] 
                              SummaryA set of generic reductions relating k-SUM and weighted graph problems are given. One interesting consequence is that finding a path on four nodes of weight zero (an innocent looking problem), truly faster than the trivial cubic time, implies breakthrough algorithms for APSP, 3SUM, and 5SUM.