Amir Abboud

134 papers A* 45A 12Journal 67Unranked 9
YearRankTypeTitle / Venue / Authors
2026 A* conf
A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection.
SODA
Amir Abboud, Shyan Akmal, Nick Fischer
2026 J jnl
Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs.
CoRR
Amir Abboud, Ron Safier, Nathan Wallheimer
2026 A conf
Triangle Detection in H-Free Graphs.
ITCS
Amir Abboud, Ron Safier, Nathan Wallheimer
2025 J jnl
A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection.
CoRR
Amir Abboud, Shyan Akmal, Nick Fischer
2025 A* conf
All-Pairs Shortest Paths with Few Weights per Node.
STOC
Amir Abboud, Nick Fischer, Ce Jin, Virginia Vassilevska Williams, Zoe Xi
2025 J jnl
All-Pairs Shortest Paths with Few Weights per Node.
CoRR
Amir Abboud, Nick Fischer, Ce Jin, Virginia Vassilevska Williams, Zoe Xi
2025 A* conf
Deterministic Almost-Linear-Time Gomory-Hu Trees.
FOCS
Amir Abboud, Rasmus Kyng, Jason Li, Debmalya Panigrahi, Maximilian Probst Gutenberg, Thatchaphol Saranurak, Weixuan Yuan, Wuwei Yuan
2025 J jnl
Deterministic Almost-Linear-Time Gomory-Hu Trees.
CoRR
Amir Abboud, Rasmus Kyng, Jason Li, Debmalya Panigrahi, Maximilian Probst Gutenberg, Thatchaphol Saranurak, Weixuan Yuan, Wuwei Yuan
2025 — conf
On Beating 2
SOSA
Amir Abboud, Rajendra Kumar
2025 J jnl
On Beating 2
CoRR
Amir Abboud, Rajendra Kumar
2025 A* conf
Recognizing Sumsets is NP-Complete.
SODA
Amir Abboud, Nick Fischer, Ron Safier, Nathan Wallheimer
2025 J jnl
Triangle Detection in H-Free Graphs.
CoRR
Amir Abboud, Ron Safier, Nathan Wallheimer
2024 — conf
Faster Combinatorial k-Clique Algorithms.
LATIN (1)
Amir Abboud, Nick Fischer, Yarin Shechter
2024 J jnl
Faster Combinatorial k-Clique Algorithms.
CoRR
Amir Abboud, Nick Fischer, Yarin Shechter
2024 A conf
From Donkeys to Kings in Tournaments.
ESA
Amir Abboud, Tomer Grossman, Moni Naor, Tomer Solomon
2024 J jnl
From Donkeys to Kings in Tournaments.
CoRR
Amir Abboud, Tomer Grossman, Moni Naor, Tomer Solomon
2024 A* conf
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms.
STOC
Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka
2024 J jnl
Reachability Preservers: New Extremal Bounds and Approximation Algorithms.
SIAM J. Comput.
Amir Abboud, Greg Bodwin
2024 J jnl
Recognizing Sumsets is NP-Complete.
CoRR
Amir Abboud, Nick Fischer, Ron Safier, Nathan Wallheimer
2024 A* conf
The Time Complexity of Fully Sparse Matrix Multiplication.
SODA
Amir Abboud, Karl Bringmann, Nick Fischer, Marvin Künnemann
2024 A conf
Worst-Case to Expander-Case Reductions: Derandomized and Generalized.
ESA
Amir Abboud, Nathan Wallheimer
2024 J jnl
Worst-Case to Expander-Case Reductions: Derandomized and Generalized.
CoRR
Amir Abboud, Nathan Wallheimer
2023 A* conf
All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time.
FOCS
Amir Abboud, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak
2023 A conf
Can You Solve Closest String Faster Than Exhaustive Search?
ESA
Amir Abboud, Nick Fischer, Elazar Goldenberg, Karthik C. S., Ron Safier
2023 J jnl
Can You Solve Closest String Faster than Exhaustive Search?
CoRR
Amir Abboud, Nick Fischer, Elazar Goldenberg, Karthik C. S., Ron Safier
2023 — conf
Listing 4-Cycles.
FSTTCS
Amir Abboud, Seri Khoury, Oree Leibowitz, Ron Safier
2023 J jnl
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms.
CoRR
Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka
2023 J jnl
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms.
Electron. Colloquium Comput. Complex.
Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka
2023 A conf
On Complexity of 1-Center in Various Metrics.
APPROX/RANDOM
Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., Saeed Seddighin
2023 A conf
On Diameter Approximation in Directed Graphs.
ESA
Amir Abboud, Mina Dalirrooyfard, Ray Li, Virginia Vassilevska Williams
2023 J jnl
On Diameter Approximation in Directed Graphs.
CoRR
Amir Abboud, Mina Dalirrooyfard, Ray Li, Virginia Vassilevska Williams
2023 — conf
On the Fine-Grained Complexity of Approximating
SOSA
Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi
2023 A* conf
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics.
STOC
Amir Abboud, Karl Bringmann, Nick Fischer
2023 J jnl
Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter.
ACM Trans. Algorithms
Amir Abboud, Fabrizio Grandoni, Virginia Vassilevska Williams
2023 J jnl
The Time Complexity of Fully Sparse Matrix Multiplication.
CoRR
Amir Abboud, Karl Bringmann, Nick Fischer, Marvin Künnemann
2023 J jnl
What Else Can Voronoi Diagrams Do For Diameter In Planar Graphs?
CoRR
Amir Abboud, Shay Mozes, Oren Weimann
2023 A conf
What Else Can Voronoi Diagrams Do for Diameter in Planar Graphs?
ESA
Amir Abboud, Shay Mozes, Oren Weimann
2023 A conf
Worst-Case to Expander-Case Reductions.
ITCS
Amir Abboud, Nathan Wallheimer
2022 A* conf
Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time.
FOCS
Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, Ohad Trabelsi
2022 A* conf
Friendly Cut Sparsifiers and Faster Gomory-Hu Trees.
SODA
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2022 J jnl
Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond.
CoRR
Amir Abboud, Karl Bringmann, Seri Khoury, Or Zamir
2022 A* conf
Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond.
STOC
Amir Abboud, Karl Bringmann, Seri Khoury, Or Zamir
2022 A* conf
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems.
ICALP
Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi
2022 J jnl
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems.
CoRR
Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi
2022 J jnl
Listing 4-Cycles.
CoRR
Amir Abboud, Seri Khoury, Oree Leibowitz, Ron Safier
2022 J jnl
SETH-based Lower Bounds for Subset Sum and Bicriteria Path.
ACM Trans. Algorithms
Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay
2022 J jnl
Scheduling lower bounds via AND subset sum.
J. Comput. Syst. Sci.
Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay
2022 J jnl
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics.
CoRR
Amir Abboud, Karl Bringmann, Nick Fischer
2022 J jnl
Worst-Case to Expander-Case Reductions.
CoRR
Amir Abboud, Nathan Wallheimer
2021 A* conf
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time.
FOCS
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2021 J jnl
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time.
CoRR
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2021 A* conf
Fine-Grained Hardness for Edit Distance to a Fixed Sequence.
ICALP
Amir Abboud, Virginia Vassilevska Williams
2021 J jnl
Friendly Cut Sparsifiers and Faster Gomory-Hu Trees.
CoRR
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2021 J jnl
Gomory-Hu Tree in Subcubic Time.
CoRR
Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, Ohad Trabelsi
2021 J jnl
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs.
Theory Comput.
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2021 J jnl
On Complexity of 1-Center in Various Metrics.
CoRR
Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., Saeed Seddighin
2021 J jnl
Smaller Cuts, Higher Lower Bounds.
ACM Trans. Algorithms
Amir Abboud, Keren Censor-Hillel, Seri Khoury, Ami Paz
2021 A* conf
Subcubic algorithms for Gomory-Hu tree in unweighted graphs.
STOC
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2020 A* conf
Cut-Equivalent Trees are Optimal for Min-Cut Queries.
FOCS
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2020 J jnl
Cut-Equivalent Trees are Optimal for Min-Cut Queries.
CoRR
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2020 J jnl
Fooling views: a new lower bound technique for distributed computations under congestion.
Distributed Comput.
Amir Abboud, Keren Censor-Hillel, Seri Khoury, Christoph Lenzen
2020 A* conf
Impossibility Results for Grammar-Compressed Linear Algebra.
NeurIPS
Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann
2020 J jnl
Impossibility Results for Grammar-Compressed Linear Algebra.
CoRR
Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann
2020 A* conf
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs.
SODA
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2020 J jnl
New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut.
CoRR
Amir Abboud, Vincent Cohen-Addad, Philip N. Klein
2020 A* conf
New hardness results for planar graph problems in p and an algorithm for sparsest cut.
STOC
Amir Abboud, Vincent Cohen-Addad, Philip N. Klein
2020 A* conf
On the Fine-Grained Complexity of Parity Problems.
ICALP
Amir Abboud, Shon Feller, Oren Weimann
2020 J jnl
On the Fine-Grained Complexity of Parity Problems.
CoRR
Amir Abboud, Shon Feller, Oren Weimann
2020 A* conf
Scheduling Lower Bounds via AND Subset Sum.
ICALP
Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay
2020 J jnl
Scheduling Lower Bounds via AND Subset Sum.
CoRR
Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay
2020 J jnl
Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs.
CoRR
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2019 A* conf
Dynamic set cover: improved algorithms and lower bounds.
STOC
Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, Barna Saha
2019 — conf
Evaluation of intel 3D-xpoint NVDIMM technology for memory-intensive genomic workloads.
MEMSYS
Daniel G. Waddington, Mark Kunitomi, Clem Dickey, Samyukta Rao, Amir Abboud, Jantz Tran
2019 A* conf
Faster Algorithms for All-Pairs Bounded Min-Cuts.
ICALP
Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemyslaw Uznanski, Daniel Wolleb-Graf
2019 A* conf
Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
ICALP
Amir Abboud
2019 J jnl
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs.
CoRR
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2019 A* conf
SETH-Based Lower Bounds for Subset Sum and Bicriteria Path.
SODA
Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay
2019 J jnl
Smaller Cuts, Higher Lower Bounds.
CoRR
Amir Abboud, Keren Censor-Hillel, Seri Khoury, Ami Paz
2019 A* conf
Subquadratic High-Dimensional Hierarchical Clustering.
NeurIPS
Amir Abboud, Vincent Cohen-Addad, Hussein Houdrouge
2018 J jnl
A Hierarchy of Lower Bounds for Sublinear Additive Spanners.
SIAM J. Comput.
Amir Abboud, Greg Bodwin, Seth Pettie
2018 A conf
Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds.
ITCS
Amir Abboud, Aviad Rubinstein
2018 J jnl
Faster Algorithms for All-Pairs Bounded Min-Cuts.
CoRR
Amir Abboud, Loukas Georgiadis, Daniel Graf, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemyslaw Uznanski
2018 J jnl
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve.
CoRR
Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann
2018 J jnl
If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser.
SIAM J. Comput.
Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams
2018 J jnl
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture.
SIAM J. Comput.
Amir Abboud, Virginia Vassilevska Williams, Huacheng Yu
2018 J jnl
More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture.
CoRR
Amir Abboud, Karl Bringmann, Holger Dell, Jesper Nederlof
2018 A* conf
More consequences of falsifying SETH and the orthogonal vectors conjecture.
STOC
Amir Abboud, Karl Bringmann, Holger Dell, Jesper Nederlof
2018 A* conf
Near-Optimal Compression for the Planar Graph Metric.
SODA
Amir Abboud, Pawel Gawrychowski, Shay Mozes, Oren Weimann
2018 A* conf
Reachability Preservers: New Extremal Bounds and Approximation Algorithms.
SODA
Amir Abboud, Greg Bodwin
2018 J jnl
Subtree Isomorphism Revisited.
ACM Trans. Algorithms
Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Or Zamir
2018 A* conf
Tighter Connections Between Formula-SAT and Shaving Logs.
ICALP
Amir Abboud, Karl Bringmann
2018 J jnl
Tighter Connections Between Formula-SAT and Shaving Logs.
CoRR
Amir Abboud, Karl Bringmann
2017 A* conf
A Hierarchy of Lower Bounds for Sublinear Additive Spanners.
SODA
Amir Abboud, Greg Bodwin, Seth Pettie
2017 A* conf
Distributed PCP Theorems for Hardness of Approximation in P.
FOCS
Amir Abboud, Aviad Rubinstein, R. Ryan Williams
2017 J jnl
Distributed PCP Theorems for Hardness of Approximation in P.
CoRR
Amir Abboud, Aviad Rubinstein
2017 A* conf
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve.
FOCS
Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann
2017 J jnl
Fooling Views: A New Lower Bound Technique for Distributed Computations under Congestion.
CoRR
Amir Abboud, Keren Censor-Hillel, Seri Khoury, Christoph Lenzen
2017 — —
Hardness in P.
Amir Abboud
2017 J jnl
Near-Optimal Compression for the Planar Graph Metric.
CoRR
Amir Abboud, Pawel Gawrychowski, Shay Mozes, Oren Weimann
2017 J jnl
Reachability Preservers: New Extremal Bounds and Approximation Algorithms.
CoRR
Amir Abboud, Greg Bodwin
2017 J jnl
SETH-Based Lower Bounds for Subset Sum and Bicriteria Path.
CoRR
Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay
2017 J jnl
The 4/3 Additive Spanner Exponent Is Tight.
J. ACM
Amir Abboud, Greg Bodwin
2017 A conf
Towards Hardness of Approximation for Polynomial Time Problems.
ITCS
Amir Abboud, Arturs Backurs
2016 J jnl
A Hierarchy of Lower Bounds for Sublinear Additive Spanners.
CoRR
Amir Abboud, Greg Bodwin, Seth Pettie
2016 A* conf
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs.
SODA
Amir Abboud, Virginia Vassilevska Williams, Joshua R. Wang
2016 A* conf
Error Amplification for Pairwise Spanner Lower Bounds.
SODA
Amir Abboud, Greg Bodwin
2016 A conf
Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks.
DISC
Amir Abboud, Keren Censor-Hillel, Seri Khoury
2016 J jnl
Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks.
CoRR
Amir Abboud, Keren Censor-Hillel, Seri Khoury
2016 A* conf
Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms.
FOCS
Amir Abboud, Søren Dahlgaard
2016 J jnl
Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms.
CoRR
Amir Abboud, Søren Dahlgaard
2016 A* conf
Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made.
STOC
Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Ryan Williams
2016 A* conf
Subtree Isomorphism Revisited.
SODA
Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Or Zamir
2016 A* conf
The 4/3 additive spanner exponent is tight.
STOC
Amir Abboud, Greg Bodwin
2015 J jnl
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter.
CoRR
Amir Abboud, Virginia Vassilevska Williams, Joshua R. Wang
2015 A* conf
If the Current Clique Algorithms are Optimal, So is Valiant's Parser.
FOCS
Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams
2015 J jnl
If the Current Clique Algorithms are Optimal, so is Valiant's Parser.
CoRR
Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams
2015 A* conf
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture.
STOC
Amir Abboud, Virginia Vassilevska Williams, Huacheng Yu
2015 A* conf
More Applications of the Polynomial Method to Algorithm Design.
SODA
Amir Abboud, Richard Ryan Williams, Huacheng Yu
2015 J jnl
Quadratic-Time Hardness of LCS and other Sequence Similarity Measures.
CoRR
Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams
2015 J jnl
Simulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made.
CoRR
Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Ryan Williams
2015 A* conf
Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter.
SODA
Amir Abboud, Fabrizio Grandoni, Virginia Vassilevska Williams
2015 J jnl
Subtree Isomorphism Revisited.
CoRR
Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Or Zamir
2015 J jnl
The 4/3 Additive Spanner Exponent is Tight.
CoRR
Amir Abboud, Greg Bodwin
2015 A* conf
Tight Hardness Results for LCS and Other Sequence Similarity Measures.
FOCS
Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams
2014 — conf
Consequences of Faster Alignment of Sequences.
ICALP (1)
Amir Abboud, Virginia Vassilevska Williams, Oren Weimann
2014 J jnl
Geometric Monitoring of Heterogeneous Streams.
IEEE Trans. Knowl. Data Eng.
Daniel Keren, Guy Sagy, Amir Abboud, David Ben-David, Assaf Schuster, Izchak Sharfman, Antonios Deligiannakis
2014 A conf
Losing Weight by Gaining Edges.
ESA
Amir Abboud, Kevin Lewi, Ryan Williams
2014 — conf
Monitoring Distributed, Heterogeneous Data Streams: The Emergence of Safe Zones.
ICAA
Daniel Keren, Guy Sagy, Amir Abboud, David Ben-David, Assaf Schuster, Izchak Sharfman, Antonios Deligiannakis
2014 A* conf
Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems.
FOCS
Amir Abboud, Virginia Vassilevska Williams
2014 J jnl
Popular conjectures imply strong lower bounds for dynamic problems.
CoRR
Amir Abboud, Virginia Vassilevska Williams
2013 J jnl
Exact Weight Subgraphs and the k-Sum Conjecture
CoRR
Amir Abboud, Kevin Lewi
2013 — conf
Exact Weight Subgraphs and the k-Sum Conjecture.
ICALP (1)
Amir Abboud, Kevin Lewi
2013 J jnl
On the parameterized complexity of k-SUM.
CoRR
Amir Abboud, Kevin Lewi, Ryan Williams
2013 — conf
Safe-Zones for Monitoring Distributed Streams.
BD3@VLDB
Daniel Keren, Guy Sagy, Amir Abboud, David Ben-David, Izchak Sharfman, Assaf Schuster