2022
-
Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, and Ohad Trabelsi:
Gomory-Hu Tree in Subcubic Time. FOCS 2022 -
Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi:
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems ICALP 2022 -
Amir Abboud, Karl Bringmann, Seri Khoury, Or Zamir:
Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond. STOC 2022 -
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
Friendly Cut Sparsifiers and Faster Gomory-Hu Trees. SODA 2022
2021
-
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time. FOCS 2021 -
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs. STOC 2021 - Amir Abboud, Virginia Vassilevska Williams:
Fine-Grained Hardness for Edit Distance to a Fixed Sequence. ICALP 2021
2020
- Amir Abboud, Keren Censor-Hillel, Seri Khoury, Christoph Lenzen:
Fooling views: a new lower bound technique for distributed computations under congestion. Distributed Comput. 33(6): 545-559 (2020) -
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
Cut-Equivalent Trees are Optimal for Min-Cut Queries. FOCS 2020: 105-118 -
Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay:
Scheduling Lower Bounds via AND Subset Sum. ICALP 2020: 4:1-4:15 -
Amir Abboud, Shon Feller, Oren Weimann:
On the Fine-Grained Complexity of Parity Problems. ICALP 2020: 5:1-5:19 -
Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann:
Impossibility Results for Grammar-Compressed Linear Algebra. NeurIPS 2020 -
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs. SODA 2020: 48-61 -
Amir Abboud, Vincent Cohen-Addad, Philip N. Klein:
New hardness results for planar graph problems in P and an algorithm for sparsest cut. STOC 2020: 996-1009
2019
- Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemyslaw Uznanski, Daniel Wolleb-Graf:
Faster Algorithms for All-Pairs Bounded Min-Cuts. ICALP 2019: 7:1-7:15 -
Amir Abboud:
Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. ICALP 2019: 8:1-8:13 -
Amir Abboud, Vincent Cohen-Addad, Hussein Houdrouge:
Subquadratic High-Dimensional Hierarchical Clustering. NeurIPS 2019: 11576-11586 -
Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay:
SETH-Based Lower Bounds for Subset Sum and Bicriteria Path. SODA 2019: 41-57 and the TALG special issue (to appear).
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. -
Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, Barna Saha:
Dynamic set cover: improved algorithms and lower bounds. STOC 2019: 114-125
2018
-
Amir Abboud, Virginia Vassilevska Williams, Huacheng Yu.:
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture. STOC 2016 and the special issue SIAM J. Comput. 47(3): 1098-1122 (2018) [slides]
Summary: The 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. -
Amir Abboud, Greg Bodwin, Seth Pettie:
A Hierarchy of Lower Bounds for Sublinear Additive Spanners. SODA 2017 and SIAM J. Comput. 47(6): 2203-2236 (2018)
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. -
Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams:
If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser. FOCS 2015 and the special issue SIAM J. Comput. 47(6): 2527-2555 (2018) [slides]
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. -
Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Or Zamir:
Subtree Isomorphism Revisited. SODA 2016 and the special issue ACM Trans. Algorithms 14(3): 27:1-27:23 (2018).
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. -
Amir Abboud, Karl Bringmann:
Tighter Connections Between Formula-SAT and Shaving Logs. ICALP 2018: 8:1-8:18 -
Amir Abboud, Aviad Rubinstein:
Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds. ITCS 2018: 35:1-35:14 -
Amir Abboud, Pawel Gawrychowski, Shay Mozes, Oren Weimann:
Near-Optimal Compression for the Planar Graph Metric. SODA 2018: 530-549
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. -
Amir Abboud, Greg Bodwin:
Reachability Preservers: New Extremal Bounds and Approximation Algorithms. SODA 2018: 1865-1883 -
Amir Abboud, Karl Bringmann, Holger Dell, Jesper Nederlof:
More consequences of falsifying SETH and the orthogonal vectors conjecture. STOC 2018: 253-266
2017
-
Amir Abboud, Aviad Rubinstein, R. Ryan Williams:
Distributed PCP Theorems for Hardness of Approximation in P. FOCS 2017: 25-36 -
A. Abboud, Greg Bodwin. [slides] STOC 2016 (best student paper) and JACM.
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. -
Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann:
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve. FOCS 2017: 192-203 -
A. Abboud, Arturs Backurs. ITCS 2017 (best student paper).
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.
2016
-
Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Ryan Williams:
Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made. STOC 2016: 375-388
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. -
A. Abboud, Keren Censor-Hillel, Seri Khoury . DISC 2016 (best student paper).
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. 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. -
A. Abboud, Greg Bodwin.
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. -
A. Abboud, Virginia Vassilevska Williams, Joshua Wang.
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.
2015
-
A. Abboud, Arturs Backurs, Virginia Vassilevska Williams.
Quadratic-Time Hardness of LCS and other Sequence Similarity Measures. FOCS 2015: 59-78.
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. -
A. Abboud, Fabrizio Grandoni, Virginia Vassilevska Williams.
Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter. SODA 2015, San Diego, CA. [slides]
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. -
A. Abboud, Ryan Williams, Huacheng Yu:
More Applications of the Polynomial Method to Algorithm Design. SODA 2015: 218-230
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.
2014
- Daniel Keren, Guy Sagy, Amir Abboud, David Ben-David, Assaf Schuster, Izchak Sharfman, Antonios Deligiannakis:
Geometric Monitoring of Heterogeneous Streams. IEEE Trans. Knowl. Data Eng. 26(8): 1890-1903 (2014) - A. Abboud, Virginia Vassilevska Williams.
Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems. FOCS 2014: 434-443. [slides]
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. - A. Abboud, Kevin Lewi, Ryan Williams.
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. - A. Abboud, Virginia Vassilevska Williams, Oren Weimann.
Consequences of Faster Alignment of Sequences. ICALP (1) 2014: 39-51. [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. - Hardness for Easy Problems. YR-ICALP 2014, Copenhagen, Denmark. [slides] (A 20-minute survey on the recent attempts to classify the poly-time problems)
2013
- A. Abboud, Kevin Lewi.
Exact Weight Subgraphs and the k-SUM Conjecture. ICALP 2013, Riga, Latvia. [slides] [pdf]
Summary: A 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.