2022

Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, and Ohad Trabelsi:
GomoryHu Tree in Subcubic Time. FOCS 2022 
Amir Abboud, Vincent CohenAddad, Euiwoong Lee, Pasin Manurangsi:
Improved Approximation Algorithms and Lower Bounds for SearchDiversification 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 GomoryHu Trees. SODA 2022
2021

Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
APMF < APSP? GomoryHu Tree for Unweighted Graphs in AlmostQuadratic Time. FOCS 2021 
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
Subcubic Algorithms for GomoryHu Tree in Unweighted Graphs. STOC 2021  Amir Abboud, Virginia Vassilevska Williams:
FineGrained Hardness for Edit Distance to a Fixed Sequence. ICALP 2021
2020
 Amir Abboud, Keren CensorHillel, Seri Khoury, Christoph Lenzen:
Fooling views: a new lower bound technique for distributed computations under congestion. Distributed Comput. 33(6): 545559 (2020) 
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
CutEquivalent Trees are Optimal for MinCut Queries. FOCS 2020: 105118 
Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay:
Scheduling Lower Bounds via AND Subset Sum. ICALP 2020: 4:14:15 
Amir Abboud, Shon Feller, Oren Weimann:
On the FineGrained Complexity of Parity Problems. ICALP 2020: 5:15:19 
Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann:
Impossibility Results for GrammarCompressed Linear Algebra. NeurIPS 2020 
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
New Algorithms and Lower Bounds for AllPairs MaxFlow in Undirected Graphs. SODA 2020: 4861 
Amir Abboud, Vincent CohenAddad, Philip N. Klein:
New hardness results for planar graph problems in P and an algorithm for sparsest cut. STOC 2020: 9961009
2019
 Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemyslaw Uznanski, Daniel WollebGraf:
Faster Algorithms for AllPairs Bounded MinCuts. ICALP 2019: 7:17:15 
Amir Abboud:
FineGrained Reductions and Quantum Speedups for Dynamic Programming. ICALP 2019: 8:18:13 
Amir Abboud, Vincent CohenAddad, Hussein Houdrouge:
Subquadratic HighDimensional Hierarchical Clustering. NeurIPS 2019: 1157611586 
Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay:
SETHBased Lower Bounds for Subset Sum and Bicriteria Path. SODA 2019: 4157 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 kSAT 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: 114125
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): 10981122 (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 STMaxFlow 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): 22032236 (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): 25272555 (2018) [slides]
Summary: kClique is reduced to recognizing a contextfree 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:127: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^{2o(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 FormulaSAT and Shaving Logs. ICALP 2018: 8:18:18 
Amir Abboud, Aviad Rubinstein:
Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds. ITCS 2018: 35:135:14 
Amir Abboud, Pawel Gawrychowski, Shay Mozes, Oren Weimann:
NearOptimal Compression for the Planar Graph Metric. SODA 2018: 530549
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: 18651883 
Amir Abboud, Karl Bringmann, Holger Dell, Jesper Nederlof:
More consequences of falsifying SETH and the orthogonal vectors conjecture. STOC 2018: 253266
2017

Amir Abboud, Aviad Rubinstein, R. Ryan Williams:
Distributed PCP Theorems for Hardness of Approximation in P. FOCS 2017: 2536 
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/3eps edges, not even compressed into n^4/3eps bits (!), while preserving the distances up to constant additive error. 
Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann:
FineGrained Complexity of Analyzing Compressed Data: Quantifying Improvements over DecompressandSolve. FOCS 2017: 192203 
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 FineGrained complexity is to prove that one cannot approximate LCS and EditDistance to within (1+eps) in nearlinear 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: 375388
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 CensorHillel, Seri Khoury . DISC 2016 (best student paper).
NearLinear 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 nearlinear 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 (denserthanbefore) 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.
QuadraticTime Hardness of LCS and other Sequence Similarity Measures. FOCS 2015: 5978.
Summary: One of the simplest problems is: what is the longest common subsequence of two strings? We show that the classic quadratictime 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: 218230
Summary: New algorithms are provided for many problems including CNFSAT 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 BenDavid, Assaf Schuster, Izchak Sharfman, Antonios Deligiannakis:
Geometric Monitoring of Heterogeneous Streams. IEEE Trans. Knowl. Data Eng. 26(8): 18901903 (2014)  A. Abboud, Virginia Vassilevska Williams.
Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems. FOCS 2014: 434443. [slides]
Summary: The trivial algorithms for many fundamental dynamic datastructures 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: kSUM on n numbers can be reduced to kClique on roughly n nodes. Moreover, nodeweighted versions of Clique and DominatingSet are not (polynomially) harder than the unweighted versions! One interesting consequence is that kSUM is (essentially) W[1]complete.  A. Abboud, Virginia Vassilevska Williams, Oren Weimann.
Consequences of Faster Alignment of Sequences. ICALP (1) 2014: 3951. [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 3SUM conjecture (from computational geometry), and give a very surprising algorithm for Min4Clique.  Hardness for Easy Problems. YRICALP 2014, Copenhagen, Denmark. [slides] (A 20minute survey on the recent attempts to classify the polytime problems)
2013
 A. Abboud, Kevin Lewi.
Exact Weight Subgraphs and the kSUM Conjecture. ICALP 2013, Riga, Latvia. [slides] [pdf]
Summary: A set of generic reductions relating kSUM 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.