Amir Abboud

Most-cited papers

Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems
Amir Abboud, Virginia Vassilevska Williams
2014IEEE Annual Symposium on Foundations of Computer Science424 citations
Semantic Scholar
Tight Hardness Results for LCS and Other Sequence Similarity Measures
Amir Abboud, A. Backurs, Virginia Vassilevska Williams
2015IEEE Annual Symposium on Foundations of Computer Science271 citations
Semantic Scholar
Consequences of Faster Alignment of Sequences
Amir Abboud, Virginia Vassilevska Williams, Oren Weimann
2014International Colloquium on Automata, Languages and Programming166 citations Open access
Semantic Scholar
More Applications of the Polynomial Method to Algorithm Design
Amir Abboud, Richard Ryan Williams, Huacheng Yu
2015ACM-SIAM Symposium on Discrete Algorithms159 citations
Semantic Scholar
Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
Amir Abboud, F. Grandoni, Virginia Vassilevska Williams
2015ACM-SIAM Symposium on Discrete Algorithms146 citations Open access
Semantic Scholar
If the Current Clique Algorithms are Optimal, So is Valiant's Parser
Amir Abboud, A. Backurs, Virginia Vassilevska Williams
2015IEEE Annual Symposium on Foundations of Computer Science140 citations Open access
Semantic Scholar
Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Ryan Williams
2015Symposium on the Theory of Computing130 citations Open access
Semantic Scholar
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
Amir Abboud, Virginia Vassilevska Williams, Huacheng Yu
2015Symposium on the Theory of Computing126 citations Open access
Semantic Scholar
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
Amir Abboud, Virginia Vassilevska Williams, Joshua R. Wang
2016ACM-SIAM Symposium on Discrete Algorithms110 citations Open access
Semantic Scholar
SETH-based Lower Bounds for Subset Sum and Bicriteria Path
Amir Abboud, K. Bringmann, Danny Hermelin, D. Shabtay
2017ACM-SIAM Symposium on Discrete Algorithms105 citations Open access
Semantic Scholar
Distributed PCP Theorems for Hardness of Approximation in P
Amir Abboud, A. Rubinstein, Ryan Williams
2017IEEE Annual Symposium on Foundations of Computer Science99 citations Open access
Semantic Scholar
The 4/3 Additive Spanner Exponent Is Tight
Amir Abboud, Greg Bodwin
2015Journal of the ACM86 citations Open access
Semantic Scholar
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter
Amir Abboud, Virginia Vassilevska Williams, Joshua R. Wang
2015arXiv.org85 citations
Semantic Scholar
A Hierarchy of Lower Bounds for Sublinear Additive Spanners
Amir Abboud, Gregory Bodwin, Seth Pettie
2016ACM-SIAM Symposium on Discrete Algorithms84 citations Open access
Semantic Scholar
Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks
Amir Abboud, K. Censor-Hillel, Seri Khoury
2016International Symposium on Distributed Computing75 citations Open access
Semantic Scholar
Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms
Amir Abboud, Søren Dahlgaard
2016IEEE Annual Symposium on Foundations of Computer Science74 citations Open access
Semantic Scholar
Exact Weight Subgraphs and the k-Sum Conjecture
Amir Abboud, Kevin Lewi
2013International Colloquium on Automata, Languages and Programming70 citations
Semantic Scholar
Losing Weight by Gaining Edges
Amir Abboud, Kevin Lewi, Ryan Williams
2013Embedded Systems and Applications65 citations
Semantic Scholar
Subtree Isomorphism Revisited
Amir Abboud, A. Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams +1 more
2015ACM-SIAM Symposium on Discrete Algorithms53 citations Open access
Semantic Scholar
More consequences of falsifying SETH and the orthogonal vectors conjecture
Amir Abboud, K. Bringmann, Holger Dell, Jesper Nederlof
2018Symposium on the Theory of Computing51 citations Open access
Semantic Scholar
Tighter Connections Between Formula-SAT and Shaving Logs
Amir Abboud, K. Bringmann
2018International Colloquium on Automata, Languages and Programming45 citations Open access
Semantic Scholar
Subcubic algorithms for Gomory–Hu tree in unweighted graphs
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2020Symposium on the Theory of Computing44 citations Open access
Semantic Scholar
Dynamic set cover: improved algorithms and lower bounds
Amir Abboud, Raghavendra Addanki, F. Grandoni, Debmalya Panigrahi +1 more
2019Symposium on the Theory of Computing44 citations
Semantic Scholar
Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds
Amir Abboud, A. Rubinstein
2018Information Technology Convergence and Services44 citations
Semantic Scholar
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve
Amir Abboud, A. Backurs, K. Bringmann, Marvin Künnemann
2017IEEE Annual Symposium on Foundations of Computer Science44 citations Open access
Semantic Scholar
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics
Amir Abboud, K. Bringmann, N. Fischer
2022Symposium on the Theory of Computing43 citations Open access
Semantic Scholar
Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond
Amir Abboud, K. Bringmann, Seri Khoury, Or Zamir
2022Symposium on the Theory of Computing43 citations Open access
Semantic Scholar
Quadratic-Time Hardness of LCS and other Sequence Similarity Measures
Amir Abboud, A. Backurs, Virginia Vassilevska Williams
2015arXiv.org43 citations
Semantic Scholar
Subquadratic High-Dimensional Hierarchical Clustering
Amir Abboud, Vincent Cohen-Addad, Hussein Houdrouge
2019Neural Information Processing Systems42 citations
Semantic Scholar
Towards Hardness of Approximation for Polynomial Time Problems
Amir Abboud, A. Backurs
2017Information Technology Convergence and Services39 citations
Semantic Scholar
Geometric Monitoring of Heterogeneous Streams
Daniel Keren, Guy Sagy, Amir Abboud, David Ben-David +3 more
2014IEEE Transactions on Knowledge and Data Engineering38 citations
Semantic Scholar
Reachability Preservers: New Extremal Bounds and Approximation Algorithms
Amir Abboud, Gregory Bodwin
2017ACM-SIAM Symposium on Discrete Algorithms37 citations
Semantic Scholar
Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time
Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi +2 more
2021IEEE Annual Symposium on Foundations of Computer Science32 citations Open access
Semantic Scholar
Smaller Cuts, Higher Lower Bounds
Amir Abboud, K. Censor-Hillel, Seri Khoury, A. Paz
2019ACM Trans. Algorithms32 citations Open access
Semantic Scholar
Fooling views: a new lower bound technique for distributed computations under congestion
Amir Abboud, K. Censor-Hillel, Seri Khoury, C. Lenzen
2017Distributed computing31 citations Open access
Semantic Scholar
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time*
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2021IEEE Annual Symposium on Foundations of Computer Science30 citations Open access
Semantic Scholar
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2019ACM-SIAM Symposium on Discrete Algorithms27 citations Open access
Semantic Scholar
Faster Algorithms for All-Pairs Bounded Min-Cuts
Amir Abboud, Loukas Georgiadis, Daniel Graf, G. Italiano +4 more
2018International Colloquium on Automata, Languages and Programming27 citations Open access
Semantic Scholar
Cut-Equivalent Trees are Optimal for Min-Cut Queries
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2020IEEE Annual Symposium on Foundations of Computer Science21 citations Open access
Semantic Scholar
The 4/3 additive spanner exponent is tight
Amir Abboud, Greg Bodwin
2016Symposium on the Theory of Computing21 citations Open access
Semantic Scholar
Evaluation of intel 3D-xpoint NVDIMM technology for memory-intensive genomic workloads
D. Waddington, Mark Kunitomi, Clem Dickey, Samyukta Rao +2 more
2019International Symposium on Memory Systems20 citations
Semantic Scholar
Error Amplification for Pairwise Spanner Lower Bounds
Amir Abboud, Gregory Bodwin
2016ACM-SIAM Symposium on Discrete Algorithms20 citations Open access
Semantic Scholar
Impossibility Results for Grammar-Compressed Linear Algebra
Amir Abboud, A. Backurs, K. Bringmann, Marvin Künnemann
2020Neural Information Processing Systems19 citations
Semantic Scholar
Scheduling Lower Bounds via AND Subset Sum
Amir Abboud, K. Bringmann, Danny Hermelin, D. Shabtay
2020International Colloquium on Automata, Languages and Programming18 citations
Semantic Scholar
Friendly Cut Sparsifiers and Faster Gomory-Hu Trees
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2021ACM-SIAM Symposium on Discrete Algorithms16 citations Open access
Semantic Scholar
Near-Optimal Compression for the Planar Graph Metric
Amir Abboud, Paweł Gawrychowski, S. Mozes, Oren Weimann
2017ACM-SIAM Symposium on Discrete Algorithms15 citations
Semantic Scholar
Listing 4-Cycles
Amir Abboud, Seri Khoury, Oree Leibowitz, Ron Safier
2022Foundations of Software Technology and Theoretical Computer Science14 citations Open access
Semantic Scholar
New hardness results for planar graph problems in p and an algorithm for sparsest cut
Amir Abboud, Vincent Cohen-Addad, P. Klein
2020Symposium on the Theory of Computing12 citations
Semantic Scholar
On the Fine-Grained Complexity of Parity Problems
Amir Abboud, S. Feller, Oren Weimann
2020International Colloquium on Automata, Languages and Programming9 citations
Semantic Scholar
Fine-Grained Reductions and Quantum Speedups for Dynamic Programming
Amir Abboud
2019International Colloquium on Automata, Languages and Programming9 citations
Semantic Scholar