Amir Abboud

ORCID

Publication Activity (10 Years)

Years Active: 2013-2024
Publications (10 Years): 97

Top Venues

Publications

Amir Abboud, Greg Bodwin
Reachability Preservers: New Extremal Bounds and Approximation Algorithms. SIAM J. Comput. 53 (2) (2024)
Amir Abboud, Nick Fischer, Yarin Shechter
Faster Combinatorial k-Clique Algorithms. LATIN (1) (2024)
Amir Abboud, Nick Fischer, Yarin Shechter
Faster Combinatorial k-Clique Algorithms. CoRR (2024)
Amir Abboud, Karl Bringmann, Nick Fischer, Marvin Künnemann
The Time Complexity of Fully Sparse Matrix Multiplication. SODA (2024)
Amir Abboud, Nathan Wallheimer
Worst-Case to Expander-Case Reductions: Derandomized and Generalized. CoRR (2024)
Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms. STOC (2024)
Amir Abboud, Nathan Wallheimer
Worst-Case to Expander-Case Reductions. ITCS (2023)
Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms. Electron. Colloquium Comput. Complex. (2023)
Amir Abboud, Seri Khoury, Oree Leibowitz, Ron Safier
Listing 4-Cycles. FSTTCS (2023)
Amir Abboud, Shay Mozes, Oren Weimann
What Else Can Voronoi Diagrams Do For Diameter In Planar Graphs? CoRR (2023)
Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi
-Center in Sparse Graphs. SOSA (2023)
Amir Abboud, Fabrizio Grandoni, Virginia Vassilevska Williams
Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter. ACM Trans. Algorithms 19 (1) (2023)
Amir Abboud, Karl Bringmann, Nick Fischer
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics. STOC (2023)
Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms. CoRR (2023)
Amir Abboud, Shay Mozes, Oren Weimann
What Else Can Voronoi Diagrams Do for Diameter in Planar Graphs? ESA (2023)
Amir Abboud, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak
All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time. FOCS (2023)
Amir Abboud, Karl Bringmann, Nick Fischer, Marvin Künnemann
The Time Complexity of Fully Sparse Matrix Multiplication. CoRR (2023)
Amir Abboud, Nick Fischer, Elazar Goldenberg, Karthik C. S., Ron Safier
Can You Solve Closest String Faster Than Exhaustive Search? ESA (2023)
Amir Abboud, Mina Dalirrooyfard, Ray Li, Virginia Vassilevska Williams
On Diameter Approximation in Directed Graphs. ESA (2023)
Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., Saeed Seddighin
On Complexity of 1-Center in Various Metrics. APPROX/RANDOM (2023)
Amir Abboud, Mina Dalirrooyfard, Ray Li, Virginia Vassilevska Williams
On Diameter Approximation in Directed Graphs. CoRR (2023)
Amir Abboud, Nick Fischer, Elazar Goldenberg, Karthik C. S., Ron Safier
Can You Solve Closest String Faster than Exhaustive Search? CoRR (2023)
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time. FOCS (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, 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. CoRR (2022)
Amir Abboud, Karl Bringmann, Nick Fischer
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics. CoRR (2022)
Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay
Scheduling lower bounds via AND subset sum. J. Comput. Syst. Sci. 127 (2022)
Amir Abboud, Seri Khoury, Oree Leibowitz, Ron Safier
Listing 4-Cycles. CoRR (2022)
Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay
SETH-based Lower Bounds for Subset Sum and Bicriteria Path. ACM Trans. Algorithms 18 (1) (2022)
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
Friendly Cut Sparsifiers and Faster Gomory-Hu Trees. SODA (2022)
Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems. CoRR (2022)
Amir Abboud, Nathan Wallheimer
Worst-Case to Expander-Case Reductions. CoRR (2022)
Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, Ohad Trabelsi
Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time. FOCS (2022)
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
Subcubic algorithms for Gomory-Hu tree in unweighted graphs. STOC (2021)
Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, Ohad Trabelsi
Gomory-Hu Tree in Subcubic Time. CoRR (2021)
Amir Abboud, Virginia Vassilevska Williams
Fine-Grained Hardness for Edit Distance to a Fixed Sequence. ICALP (2021)
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time. CoRR (2021)
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
Friendly Cut Sparsifiers and Faster Gomory-Hu Trees. CoRR (2021)
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time. FOCS (2021)
Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., Saeed Seddighin
On Complexity of 1-Center in Various Metrics. CoRR (2021)
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs. Theory Comput. 17 (2021)
Amir Abboud, Keren Censor-Hillel, Seri Khoury, Ami Paz
Smaller Cuts, Higher Lower Bounds. ACM Trans. Algorithms 17 (4) (2021)
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
Cut-Equivalent Trees are Optimal for Min-Cut Queries. CoRR (2020)
Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann
Impossibility Results for Grammar-Compressed Linear Algebra. NeurIPS (2020)
Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann
Impossibility Results for Grammar-Compressed Linear Algebra. CoRR (2020)
Amir Abboud, Shon Feller, Oren Weimann
On the Fine-Grained Complexity of Parity Problems. CoRR (2020)
Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay
Scheduling Lower Bounds via AND Subset Sum. CoRR (2020)
Amir Abboud, Vincent Cohen-Addad, Philip N. Klein
New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut. CoRR (2020)
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs. CoRR (2020)
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)
Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay
Scheduling Lower Bounds via AND Subset Sum. ICALP (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) (2020)
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
Cut-Equivalent Trees are Optimal for Min-Cut Queries. FOCS (2020)
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs. SODA (2020)
Amir Abboud, Shon Feller, Oren Weimann
On the Fine-Grained Complexity of Parity Problems. ICALP (2020)
Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay
SETH-Based Lower Bounds for Subset Sum and Bicriteria Path. SODA (2019)
Amir Abboud, Keren Censor-Hillel, Seri Khoury, Ami Paz
Smaller Cuts, Higher Lower Bounds. CoRR (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)
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs. CoRR (2019)
Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, Barna Saha
Dynamic set cover: improved algorithms and lower bounds. STOC (2019)
Daniel G. Waddington, Mark Kunitomi, Clem Dickey, Samyukta Rao, Amir Abboud, Jantz Tran
Evaluation of intel 3D-xpoint NVDIMM technology for memory-intensive genomic workloads. MEMSYS (2019)
Amir Abboud
Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. ICALP (2019)
Amir Abboud, Vincent Cohen-Addad, Hussein Houdrouge
Subquadratic High-Dimensional Hierarchical Clustering. NeurIPS (2019)
Amir Abboud, Greg Bodwin, Seth Pettie
A Hierarchy of Lower Bounds for Sublinear Additive Spanners. SIAM J. Comput. 47 (6) (2018)
Amir Abboud, Loukas Georgiadis, Daniel Graf, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemyslaw Uznanski
Faster Algorithms for All-Pairs Bounded Min-Cuts. CoRR (2018)
Amir Abboud, Greg Bodwin
Reachability Preservers: New Extremal Bounds and Approximation Algorithms. SODA (2018)
Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve. CoRR (2018)
Amir Abboud, Aviad Rubinstein
Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds. ITCS (2018)
Amir Abboud, Karl Bringmann, Holger Dell, Jesper Nederlof
More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture. CoRR (2018)
Amir Abboud, Virginia Vassilevska Williams, Huacheng Yu
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture. SIAM J. Comput. 47 (3) (2018)
Amir Abboud, Pawel Gawrychowski, Shay Mozes, Oren Weimann
Near-Optimal Compression for the Planar Graph Metric. SODA (2018)
Amir Abboud, Karl Bringmann
Tighter Connections Between Formula-SAT and Shaving Logs. CoRR (2018)
Amir Abboud, Karl Bringmann
Tighter Connections Between Formula-SAT and Shaving Logs. ICALP (2018)
Amir Abboud, Karl Bringmann, Holger Dell, Jesper Nederlof
More consequences of falsifying SETH and the orthogonal vectors conjecture. STOC (2018)
Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams
If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser. SIAM J. Comput. 47 (6) (2018)
Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Or Zamir
Subtree Isomorphism Revisited. ACM Trans. Algorithms 14 (3) (2018)
Amir Abboud, Greg Bodwin
Reachability Preservers: New Extremal Bounds and Approximation Algorithms. CoRR (2017)
Amir Abboud, Greg Bodwin
The 4/3 Additive Spanner Exponent Is Tight. J. ACM 64 (4) (2017)
Amir Abboud, Pawel Gawrychowski, Shay Mozes, Oren Weimann
Near-Optimal Compression for the Planar Graph Metric. CoRR (2017)
Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay
SETH-Based Lower Bounds for Subset Sum and Bicriteria Path. CoRR (2017)
Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve. FOCS (2017)
Amir Abboud, Greg Bodwin, Seth Pettie
A Hierarchy of Lower Bounds for Sublinear Additive Spanners. SODA (2017)
Amir Abboud, Aviad Rubinstein, R. Ryan Williams
Distributed PCP Theorems for Hardness of Approximation in P. FOCS (2017)
Amir Abboud, Keren Censor-Hillel, Seri Khoury, Christoph Lenzen
Fooling Views: A New Lower Bound Technique for Distributed Computations under Congestion. CoRR (2017)
Amir Abboud, Arturs Backurs
Towards Hardness of Approximation for Polynomial Time Problems. ITCS (2017)
Amir Abboud, Aviad Rubinstein
Distributed PCP Theorems for Hardness of Approximation in P. CoRR (2017)
Amir Abboud, Keren Censor-Hillel, Seri Khoury
Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks. CoRR (2016)
Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Or Zamir
Subtree Isomorphism Revisited. SODA (2016)
Amir Abboud, Greg Bodwin, Seth Pettie
A Hierarchy of Lower Bounds for Sublinear Additive Spanners. CoRR (2016)
Amir Abboud, Søren Dahlgaard
Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms. CoRR (2016)
Amir Abboud, Virginia Vassilevska Williams, Joshua R. Wang
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs. SODA (2016)
Amir Abboud, Søren Dahlgaard
Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms. FOCS (2016)
Amir Abboud, Greg Bodwin
The 4/3 additive spanner exponent is tight. STOC (2016)
Amir Abboud, Keren Censor-Hillel, Seri Khoury
Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks. DISC (2016)
Amir Abboud, Greg Bodwin
Error Amplification for Pairwise Spanner Lower Bounds. SODA (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)
Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Or Zamir
Subtree Isomorphism Revisited. CoRR (2015)
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. CoRR (2015)
Amir Abboud, Virginia Vassilevska Williams, Joshua R. Wang
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter. CoRR (2015)

Amir Abboud.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Amir Abboud