43 citations · 127 across the 22 of their papers we have counts for
42 papers
On Diameter Approximation in Directed Graphs
Amir Abboud, Mina Dalirrooyfard, Ray Li +1
Computing the diameter of a graph, i.e. the largest distance, is a fundamental problem that is central in fine-grained complexity. In undirected graphs, the Strong Exponential Time…
Can You Solve Closest String Faster than Exhaustive Search?
Amir Abboud, Nick Fischer, Elazar Goldenberg +2
We study the fundamental problem of finding the best string to represent a given set, in the form of the Closest String problem: Given a set of strings, find…
What Else Can Voronoi Diagrams Do For Diameter In Planar Graphs?
Amir Abboud, Shay Mozes, Oren Weimann
The Voronoi diagrams technique was introduced by Cabello to compute the diameter of planar graphs in subquadratic time. We present novel applications of this technique in static, f…
Worst-Case to Expander-Case Reductions
Amir Abboud, Nathan Wallheimer
In recent years, the expander decomposition method was used to develop many graph algorithms, resulting in major improvements to longstanding complexity barriers. This powerful ham…
Listing 4-Cycles
Amir Abboud, Seri Khoury, Oree Leibowitz +1
In this note we present an algorithm that lists all -cycles in a graph in time where is their number. Notably, this separates -cycle list…
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics
Amir Abboud, Karl Bringmann, Nick Fischer
The "short cycle removal" technique was recently introduced by Abboud, Bringmann, Khoury and Zamir (STOC '22) to prove fine-grained hardness of approximation. Its main technical re…