AAAmir Abboud

Amir Abboud

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Amir Abboud has a total of 31 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    All-Pairs Shortest Paths with Few Weights per Node

    by Amir Abboud, Nick Fischer, Ce Jin, Virginia Vassilevska Williams, Zoe Xi


  • Open Access

    New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms

    by Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka

    We revisit the fundamental Boolean Matrix Multiplication (BMM) problem. With the invention of algebraic fast matrix multiplication over 50 years ago, it also became known that BMM can be solved in truly subcubic O(nω) time, where ωO(n3)-time algorithm was initially improved by a log2n factor [Arlazarov et al.; RAS’70], then by log2.25n [Bansal and Williams; FOCS’09], then by log3n [Chan; SODA’15], and finally by log4n [Yu; ICALP’15]. We design a combinatorial algorithm for BMM running in time n3 / 2Ω((logn)1/7) – a speed-up over cubic time that is stronger than any poly-log factor. This comes tantalizingly close to refuting the conjecture from the 90s that truly subcubic combinatorial algorithms for BMM are impossible. This popular conjecture is the basis for dozens of fine-grained hardness results. Our main technical contribution is a new regularity decomposition theorem for Boolean matrices (or equivalently, bipartite graphs) under a notion of regularity that was recently introduced and analyzed analytically in the context of communication complexity [Kelley, Lovett, Meka; STOC’24], and is related to a similar notion from the recent work on 3-term arithmetic progression free sets [Kelley, Meka; FOCS’23].


  • All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time

    by Amir Abboud, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak

    A Gomory-Hu tree (also called a cut tree) succinctly represents $(s, t)$ min-cuts (and therefore, $(s, t)$ max-flow values) of all pairs of vertices $s, t$ in an undirected graph. In this paper, we give an $m^{1+o(1)}$-time algorithm for constructing a Gomory-Hu tree for a graph with m edges. This shows that the all-pairs max-flows problem has the same running time as the single-pair max-flow problem, up to a subpolynomial factor. Prior to our work, the best known Gomory-Hu tree algorithm was obtained in recent work by Abboud et al. (FOCS 2022) and requires $\tilde{O}\left(n^{2}\right)$ time for a graph with n vertices. Our result marks a natural culmination of over 60 years of research into the all-pairs maxflows problem that started with Gomory and Hu’s pathbreaking result introducing the Gomory-Hu tree in 1961.


  • Open Access

    Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter

    by Amir Abboud, Fabrizio Grandoni, Virginia Vassilevska Williams

    Measuring the importance of a node in a network is a major goal in the analysis of social networks, biological systems, transportation networks, and so forth. Different centrality measures have been proposed to capture the notion of node importance. For example, the center of a graph is a node that minimizes the maximum distance to any other node (the latter distance is the radius of the graph). The median of a graph is a node that minimizes the sum of the distances to all other nodes. Informally, the betweenness centrality of a node w measures the fraction of shortest paths that have w as an intermediate node. Finally, the reach centrality of a node w is the smallest distance r such that any s - t shortest path passing through w has either s or t in the ball of radius r around w . The fastest known algorithms to compute the center and the median of a graph and to compute the betweenness or reach centrality even of a single node take roughly cubic time in the number n of nodes in the input graph. It is open whether these problems admit truly subcubic algorithms, i.e., algorithms with running time Õ(n 3-δ ) for some constant δ > 0. 1 We relate the complexity of the mentioned centrality problems to two classical problems for which no truly subcubic algorithm is known, namely All Pairs Shortest Paths (APSP) and Diameter. We show that Radius, Median, and Betweenness Centrality are equivalent under subcubic reductions to APSP, i.e., that a truly subcubic algorithm for any of these problems implies a truly subcubic algorithm for all of them. We then show that Reach Centrality is equivalent to Diameter under subcubic reductions. The same holds for the problem of approximating Betweenness Centrality within any finite factor. Thus, the latter two centrality problems could potentially be solved in truly subcubic time, even if APSP required essentially cubic time. On the positive side, our reductions for Reach Centrality imply an improved Õ(Mn ω )-time algorithm for this problem in case of non-negative integer weights upper bounded by M , where ω is a fast matrix multiplication exponent.


  • Open Access

    SETH-Based Lower Bounds for Subset Sum and Bicriteria Path

    by Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay

    Subset-Sum and k-SAT are two of the most extensively studied problems in computer science, and conjectures about their hardness are among the cornerstones of fine-grained complexity. One of the most intriguing open problems in this area is to base the hardness of one of these problems on the other. Our main result is a tight reduction from k-SAT to Subset-Sum on dense instances, proving that Bellman's 1962 pseudo-polynomial $O^{*}(T)$-time algorithm for Subset-Sum on $n$ numbers and target $T$ cannot be improved to time $T^{1-\varepsilon}\cdot 2^{o(n)}$ for any $\varepsilon>0$, unless the Strong Exponential Time Hypothesis (SETH) fails. This is one of the strongest known connections between any two of the core problems of fine-grained complexity. As a corollary, we prove a "Direct-OR" theorem for Subset-Sum under SETH, offering a new tool for proving conditional lower bounds: It is now possible to assume that deciding whether one out of $N$ given instances of Subset-Sum is a YES instance requires time $(N T)^{1-o(1)}$. As an application of this corollary, we prove a tight SETH-based lower bound for the classical Bicriteria s,t-Path problem, which is extensively studied in Operations Research. We separate its complexity from that of Subset-Sum: On graphs with $m$ edges and edge lengths bounded by $L$, we show that the $O(Lm)$ pseudo-polynomial time algorithm by Joksch from 1966 cannot be improved to $\tilde{O}(L+m)$, in contrast to a recent improvement for Subset Sum (Bringmann, SODA 2017).

  • Open Access

    Tighter Connections Between Formula-SAT and Shaving Logs

    by Amir Abboud, Karl Bringmann

    A noticeable fraction of Algorithms papers in the last few decades improve the running time of well-known algorithms for fundamental problems by logarithmic factors. For example, the $O(n^2)$ dynamic programming solution to the Longest Common Subsequence problem (LCS) was improved to $O(n^2/\log^2 n)$ in several ways and using a variety of ingenious tricks. This line of research, also known as "the art of shaving log factors", lacks a tool for proving negative results. Specifically, how can we show that it is unlikely that LCS can be solved in time $O(n^2/\log^3 n)$? Perhaps the only approach for such results was suggested in a recent paper of Abboud, Hansen, Vassilevska W. and Williams (STOC'16). The authors blame the hardness of shaving logs on the hardness of solving satisfiability on Boolean formulas (Formula-SAT) faster than exhaustive search. They show that an $O(n^2/\log^{1000} n)$ algorithm for LCS would imply a major advance in circuit lower bounds. Whether this approach can lead to tighter barriers was unclear. In this paper, we push this approach to its limit and, in particular, prove that a well-known barrier from complexity theory stands in the way for shaving five additional log factors for fundamental combinatorial problems. For LCS, regular expression pattern matching, as well as the Fr\'echet distance problem from Computational Geometry, we show that an $O(n^2/\log^{7+\varepsilon} n)$ runtime would imply new Formula-SAT algorithms. Our main result is a reduction from SAT on formulas of size $s$ over $n$ variables to LCS on sequences of length $N=2^{n/2} \cdot s^{1+o(1)}$. Our reduction is essentially as efficient as possible, and it greatly improves the previously known reduction for LCS with $N=2^{n/2} \cdot s^c$, for some $c \geq 100$.

  • Open Access

    Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve

    by Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann

    Can we analyze data without decompressing it? As our data keeps growing, understanding the time complexity of problems on compressed inputs, rather than in convenient uncompressed forms, becomes more and more relevant. Suppose we are given a compression of size $n$ of data that originally has size $N$, and we want to solve a problem with time complexity $T(\cdot)$. The naive strategy of "decompress-and-solve" gives time $T(N)$, whereas "the gold standard" is time $T(n)$: to analyze the compression as efficiently as if the original data was small. We restrict our attention to data in the form of a string (text, files, genomes, etc.) and study the most ubiquitous tasks. While the challenge might seem to depend heavily on the specific compression scheme, most methods of practical relevance (Lempel-Ziv-family, dictionary methods, and others) can be unified under the elegant notion of Grammar Compressions. A vast literature, across many disciplines, established this as an influential notion for Algorithm design. We introduce a framework for proving (conditional) lower bounds in this field, allowing us to assess whether decompress-and-solve can be improved, and by how much. Our main results are: - The $O(nN\sqrt{\log{N/n}})$ bound for LCS and the $O(\min\{N \log N, nM\})$ bound for Pattern Matching with Wildcards are optimal up to $N^{o(1)}$ factors, under the Strong Exponential Time Hypothesis. (Here, $M$ denotes the uncompressed length of the compressed pattern.) - Decompress-and-solve is essentially optimal for Context-Free Grammar Parsing and RNA Folding, under the $k$-Clique conjecture. - We give an algorithm showing that decompress-and-solve is not optimal for Disjointness.

  • Open Access

    Near-Optimal Compression for the Planar Graph Metric

    by Amir Abboud, Pawel Gawrychowski, Shay Mozes, Oren Weimann

    The Planar Graph Metric Compression Problem is to compactly encode the distances among $k$ nodes in a planar graph of size $n$. Two na\"ive solutions are to store the graph using $O(n)$ bits, or to explicitly store the distance matrix with $O(k^2 \log{n})$ bits. The only lower bounds are from the seminal work of Gavoille, Peleg, Prennes, and Raz [SODA'01], who rule out compressions into a polynomially smaller number of bits, for {\em weighted} planar graphs, but leave a large gap for unweighted planar graphs. For example, when $k=\sqrt{n}$, the upper bound is $O(n)$ and their constructions imply an $\Omega(n^{3/4})$ lower bound. This gap is directly related to other major open questions in labelling schemes, dynamic algorithms, and compact routing. Our main result is a new compression of the planar graph metric into $\tilde{O}(\min (k^2 , \sqrt{k\cdot n}))$ bits, which is optimal up to log factors. Our data structure breaks an $\Omega(k^2)$ lower bound of Krauthgamer, Nguyen, and Zondiner [SICOMP'14] for compression using minors, and the lower bound of Gavoille et al. for compression of weighted planar graphs. This is an unexpected and decisive proof that weights can make planar graphs inherently more complex. Moreover, we design a new {\em Subset Distance Oracle} for planar graphs with $\tilde O(\sqrt{k\cdot n})$ space, and $\tilde O(n^{3/4})$ query time. Our work carries strong messages to related fields. In particular, the famous $O(n^{1/2})$ vs. $\Omega(n^{1/3})$ gap for distance labelling schemes in planar graphs {\em cannot} be resolved with the current lower bound techniques.

  • Open Access

    A Hierarchy of Lower Bounds for Sublinear Additive Spanners

    by Amir Abboud, Greg Bodwin, Seth Pettie

    Spanners, emulators, and approximate distance oracles can be viewed as lossy compression schemes that represent an unweighted graph metric in small space, say $\tilde{O}(n^{1+\delta})$ bits. There is an inherent tradeoff between the sparsity parameter $\delta$ and the stretch function $f$ of the compression scheme, but the qualitative nature of this tradeoff has remained a persistent open problem. In this paper we show that the recent additive spanner lower bound of Abboud and Bodwin is just the first step in a hierarchy of lower bounds that fully characterize the asymptotic behavior of the optimal stretch function $f$ as a function of $\delta \in (0,1/3)$. Specifically, for any integer $k\ge 2$, any compression scheme with size $O(n^{1+\frac{1}{2^k-1} - \epsilon})$ has a sublinear additive stretch function $f$: $$f(d) = d + \Omega(d^{1-\frac{1}{k}}).$$ This lower bound matches Thorup and Zwick's (2006) construction of sublinear additive emulators. It also shows that Elkin and Peleg's $(1+\epsilon,\beta)$-spanners have an essentially optimal tradeoff between $\delta,\epsilon,$ and $\beta$, and that the sublinear additive spanners of Pettie (2009) and Chechik (2013) are not too far from optimal. To complement these lower bounds we present a new construction of $(1+\epsilon, O(k/\epsilon)^{k-1})$-spanners with size $O((k/\epsilon)^{h_k} kn^{1+\frac{1}{2^{k+1}-1}})$, where $h_k < 3/4$. This size bound improves on the spanners of Elkin and Peleg (2004), Thorup and Zwick (2006), and Pettie (2009). According to our lower bounds neither the size nor stretch function can be substantially improved.