default search action
Amir Abboud
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [j13]Amir Abboud, Greg Bodwin:
Reachability Preservers: New Extremal Bounds and Approximation Algorithms. SIAM J. Comput. 53(2): 221-246 (2024) - [c60]Amir Abboud, Tomer Grossman, Moni Naor, Tomer Solomon:
From Donkeys to Kings in Tournaments. ESA 2024: 3:1-3:14 - [c59]Amir Abboud, Nathan Wallheimer:
Worst-Case to Expander-Case Reductions: Derandomized and Generalized. ESA 2024: 4:1-4:18 - [c58]Amir Abboud, Nick Fischer, Yarin Shechter:
Faster Combinatorial k-Clique Algorithms. LATIN (1) 2024: 193-206 - [c57]Amir Abboud, Karl Bringmann, Nick Fischer, Marvin Künnemann:
The Time Complexity of Fully Sparse Matrix Multiplication. SODA 2024: 4670-4703 - [c56]Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka:
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms. STOC 2024: 935-943 - [i46]Amir Abboud, Nick Fischer, Yarin Shechter:
Faster Combinatorial k-Clique Algorithms. CoRR abs/2401.13502 (2024) - [i45]Amir Abboud, Nathan Wallheimer:
Worst-Case to Expander-Case Reductions: Derandomized and Generalized. CoRR abs/2403.08394 (2024) - 2023
- [j12]Amir Abboud, Fabrizio Grandoni, Virginia Vassilevska Williams:
Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter. ACM Trans. Algorithms 19(1): 3:1-3:30 (2023) - [c55]Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., Saeed Seddighin:
On Complexity of 1-Center in Various Metrics. APPROX/RANDOM 2023: 1:1-1:19 - [c54]Amir Abboud, Mina Dalirrooyfard, Ray Li, Virginia Vassilevska Williams:
On Diameter Approximation in Directed Graphs. ESA 2023: 2:1-2:17 - [c53]Amir Abboud, Nick Fischer, Elazar Goldenberg, Karthik C. S., Ron Safier:
Can You Solve Closest String Faster Than Exhaustive Search? ESA 2023: 3:1-3:17 - [c52]Amir Abboud, Shay Mozes, Oren Weimann:
What Else Can Voronoi Diagrams Do for Diameter in Planar Graphs? ESA 2023: 4:1-4:20 - [c51]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: 2204-2212 - [c50]Amir Abboud, Seri Khoury, Oree Leibowitz, Ron Safier:
Listing 4-Cycles. FSTTCS 2023: 25:1-25:16 - [c49]Amir Abboud, Nathan Wallheimer:
Worst-Case to Expander-Case Reductions. ITCS 2023: 1:1-1:23 - [c48]Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi:
On the Fine-Grained Complexity of Approximating k-Center in Sparse Graphs. SOSA 2023: 145-155 - [c47]Amir Abboud, Karl Bringmann, Nick Fischer:
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics. STOC 2023: 391-404 - [i44]Amir Abboud, Shay Mozes, Oren Weimann:
What Else Can Voronoi Diagrams Do For Diameter In Planar Graphs? CoRR abs/2305.02946 (2023) - [i43]Amir Abboud, Nick Fischer, Elazar Goldenberg, Karthik C. S., Ron Safier:
Can You Solve Closest String Faster than Exhaustive Search? CoRR abs/2305.16878 (2023) - [i42]Amir Abboud, Mina Dalirrooyfard, Ray Li, Virginia Vassilevska Williams:
On Diameter Approximation in Directed Graphs. CoRR abs/2307.07583 (2023) - [i41]Amir Abboud, Karl Bringmann, Nick Fischer, Marvin Künnemann:
The Time Complexity of Fully Sparse Matrix Multiplication. CoRR abs/2309.06317 (2023) - [i40]Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka:
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms. CoRR abs/2311.09095 (2023) - [i39]Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka:
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [j11]Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay:
Scheduling lower bounds via AND subset sum. J. Comput. Syst. Sci. 127: 29-40 (2022) - [j10]Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay:
SETH-based Lower Bounds for Subset Sum and Bicriteria Path. ACM Trans. Algorithms 18(1): 6:1-6:22 (2022) - [c46]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: 884-895 - [c45]Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi:
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems. ICALP 2022: 7:1-7:18 - [c44]Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
Friendly Cut Sparsifiers and Faster Gomory-Hu Trees. SODA 2022: 3630-3649 - [c43]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: 1487-1500 - [i38]Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi:
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems. CoRR abs/2203.01857 (2022) - [i37]Amir Abboud, Karl Bringmann, Seri Khoury, Or Zamir:
Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond. CoRR abs/2204.10465 (2022) - [i36]Amir Abboud, Karl Bringmann, Nick Fischer:
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics. CoRR abs/2211.07058 (2022) - [i35]Amir Abboud, Seri Khoury, Oree Leibowitz, Ron Safier:
Listing 4-Cycles. CoRR abs/2211.10022 (2022) - [i34]Amir Abboud, Nathan Wallheimer:
Worst-Case to Expander-Case Reductions. CoRR abs/2211.12833 (2022) - 2021
- [j9]Amir Abboud, Keren Censor-Hillel, Seri Khoury, Ami Paz:
Smaller Cuts, Higher Lower Bounds. ACM Trans. Algorithms 17(4): 30:1-30:40 (2021) - [j8]Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs. Theory Comput. 17: 1-27 (2021) - [c42]Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time. FOCS 2021: 1135-1146 - [c41]Amir Abboud, Virginia Vassilevska Williams:
Fine-Grained Hardness for Edit Distance to a Fixed Sequence. ICALP 2021: 7:1-7:14 - [c40]Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
Subcubic algorithms for Gomory-Hu tree in unweighted graphs. STOC 2021: 1725-1737 - [i33]Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time. CoRR abs/2106.02981 (2021) - [i32]Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
Friendly Cut Sparsifiers and Faster Gomory-Hu Trees. CoRR abs/2110.15891 (2021) - [i31]Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, Ohad Trabelsi:
Gomory-Hu Tree in Subcubic Time. CoRR abs/2111.04958 (2021) - [i30]Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., Saeed Seddighin:
On Complexity of 1-Center in Various Metrics. CoRR abs/2112.03222 (2021) - 2020
- [j7]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): 545-559 (2020) - [c39]Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
Cut-Equivalent Trees are Optimal for Min-Cut Queries. FOCS 2020: 105-118 - [c38]Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay:
Scheduling Lower Bounds via AND Subset Sum. ICALP 2020: 4:1-4:15 - [c37]Amir Abboud, Shon Feller, Oren Weimann:
On the Fine-Grained Complexity of Parity Problems. ICALP 2020: 5:1-5:19 - [c36]Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann:
Impossibility Results for Grammar-Compressed Linear Algebra. NeurIPS 2020 - [c35]Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs. SODA 2020: 48-61 - [c34]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: 996-1009 - [i29]Amir Abboud, Shon Feller, Oren Weimann:
On the Fine-Grained Complexity of Parity Problems. CoRR abs/2002.07415 (2020) - [i28]Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay:
Scheduling Lower Bounds via AND Subset Sum. CoRR abs/2003.07113 (2020) - [i27]Amir Abboud, Vincent Cohen-Addad, Philip N. Klein:
New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut. CoRR abs/2007.02377 (2020) - [i26]Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
Cut-Equivalent Trees are Optimal for Min-Cut Queries. CoRR abs/2009.06090 (2020) - [i25]Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann:
Impossibility Results for Grammar-Compressed Linear Algebra. CoRR abs/2010.14181 (2020) - [i24]Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs. CoRR abs/2012.10281 (2020)
2010 – 2019
- 2019
- [c33]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: 7:1-7:15 - [c32]Amir Abboud:
Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. ICALP 2019: 8:1-8:13 - [c31]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: 277-287 - [c30]Amir Abboud, Vincent Cohen-Addad, Hussein Houdrouge:
Subquadratic High-Dimensional Hierarchical Clustering. NeurIPS 2019: 11576-11586 - [c29]Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay:
SETH-Based Lower Bounds for Subset Sum and Bicriteria Path. SODA 2019: 41-57 - [c28]Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, Barna Saha:
Dynamic set cover: improved algorithms and lower bounds. STOC 2019: 114-125 - [i23]Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs. CoRR abs/1901.01412 (2019) - [i22]Amir Abboud, Keren Censor-Hillel, Seri Khoury, Ami Paz:
Smaller Cuts, Higher Lower Bounds. CoRR abs/1901.01630 (2019) - 2018
- [j6]Amir Abboud, Virginia Vassilevska Williams, Huacheng Yu:
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture. SIAM J. Comput. 47(3): 1098-1122 (2018) - [j5]Amir Abboud, Greg Bodwin, Seth Pettie:
A Hierarchy of Lower Bounds for Sublinear Additive Spanners. SIAM J. Comput. 47(6): 2203-2236 (2018) - [j4]Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams:
If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser. SIAM J. Comput. 47(6): 2527-2555 (2018) - [j3]Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Or Zamir:
Subtree Isomorphism Revisited. ACM Trans. Algorithms 14(3): 27:1-27:23 (2018) - [c27]Amir Abboud, Karl Bringmann:
Tighter Connections Between Formula-SAT and Shaving Logs. ICALP 2018: 8:1-8:18 - [c26]Amir Abboud, Aviad Rubinstein:
Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds. ITCS 2018: 35:1-35:14 - [c25]Amir Abboud, Pawel Gawrychowski, Shay Mozes, Oren Weimann:
Near-Optimal Compression for the Planar Graph Metric. SODA 2018: 530-549 - [c24]Amir Abboud, Greg Bodwin:
Reachability Preservers: New Extremal Bounds and Approximation Algorithms. SODA 2018: 1865-1883 - [c23]Amir Abboud, Karl Bringmann, Holger Dell, Jesper Nederlof:
More consequences of falsifying SETH and the orthogonal vectors conjecture. STOC 2018: 253-266 - [i21]Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann:
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve. CoRR abs/1803.00796 (2018) - [i20]Amir Abboud, Karl Bringmann:
Tighter Connections Between Formula-SAT and Shaving Logs. CoRR abs/1804.08978 (2018) - [i19]Amir Abboud, Karl Bringmann, Holger Dell, Jesper Nederlof:
More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture. CoRR abs/1805.08554 (2018) - [i18]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 abs/1807.05803 (2018) - 2017
- [b1]Amir Abboud:
Hardness in P. Stanford University, USA, 2017 - [j2]Amir Abboud, Greg Bodwin:
The 4/3 Additive Spanner Exponent Is Tight. J. ACM 64(4): 28:1-28:20 (2017) - [c22]Amir Abboud, Aviad Rubinstein, R. Ryan Williams:
Distributed PCP Theorems for Hardness of Approximation in P. FOCS 2017: 25-36 - [c21]Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann:
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve. FOCS 2017: 192-203 - [c20]Amir Abboud, Arturs Backurs:
Towards Hardness of Approximation for Polynomial Time Problems. ITCS 2017: 11:1-11:26 - [c19]Amir Abboud, Greg Bodwin, Seth Pettie:
A Hierarchy of Lower Bounds for Sublinear Additive Spanners. SODA 2017: 568-576 - [i17]Amir Abboud, Pawel Gawrychowski, Shay Mozes, Oren Weimann:
Near-Optimal Compression for the Planar Graph Metric. CoRR abs/1703.04814 (2017) - [i16]Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay:
SETH-Based Lower Bounds for Subset Sum and Bicriteria Path. CoRR abs/1704.04546 (2017) - [i15]Amir Abboud, Aviad Rubinstein:
Distributed PCP Theorems for Hardness of Approximation in P. CoRR abs/1706.06407 (2017) - [i14]Amir Abboud, Greg Bodwin:
Reachability Preservers: New Extremal Bounds and Approximation Algorithms. CoRR abs/1710.11250 (2017) - [i13]Amir Abboud, Keren Censor-Hillel, Seri Khoury, Christoph Lenzen:
Fooling Views: A New Lower Bound Technique for Distributed Computations under Congestion. CoRR abs/1711.01623 (2017) - 2016
- [c18]Amir Abboud, Søren Dahlgaard:
Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms. FOCS 2016: 477-486 - [c17]Amir Abboud, Virginia Vassilevska Williams, Joshua R. Wang:
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs. SODA 2016: 377-391 - [c16]Amir Abboud, Greg Bodwin:
Error Amplification for Pairwise Spanner Lower Bounds. SODA 2016: 841-854 - [c15]Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Or Zamir:
Subtree Isomorphism Revisited. SODA 2016: 1256-1271 - [c14]Amir Abboud, Greg Bodwin:
The 4/3 additive spanner exponent is tight. STOC 2016: 351-361 - [c13]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: 375-388 - [c12]Amir Abboud, Keren Censor-Hillel, Seri Khoury:
Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks. DISC 2016: 29-42 - [i12]Amir Abboud, Søren Dahlgaard:
Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms. CoRR abs/1605.03797 (2016) - [i11]Amir Abboud, Keren Censor-Hillel, Seri Khoury:
Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks. CoRR abs/1605.05109 (2016) - [i10]Amir Abboud, Greg Bodwin, Seth Pettie:
A Hierarchy of Lower Bounds for Sublinear Additive Spanners. CoRR abs/1607.07497 (2016) - 2015
- [c11]Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams:
Tight Hardness Results for LCS and Other Sequence Similarity Measures. FOCS 2015: 59-78 - [c10]Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams:
If the Current Clique Algorithms are Optimal, So is Valiant's Parser. FOCS 2015: 98-117 - [c9]Amir Abboud, Richard Ryan Williams, Huacheng Yu:
More Applications of the Polynomial Method to Algorithm Design. SODA 2015: 218-230 - [c8]Amir Abboud, Fabrizio Grandoni, Virginia Vassilevska Williams:
Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter. SODA 2015: 1681-1697 - [c7]Amir Abboud, Virginia Vassilevska Williams, Huacheng Yu:
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture. STOC 2015: 41-50 - [i9]Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams:
Quadratic-Time Hardness of LCS and other Sequence Similarity Measures. CoRR abs/1501.07053 (2015) - [i8]Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams:
If the Current Clique Algorithms are Optimal, so is Valiant's Parser. CoRR abs/1504.01431 (2015) - [i7]Amir Abboud, Virginia Vassilevska Williams, Joshua R. Wang:
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter. CoRR abs/1506.01799 (2015) - [i6]Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Or Zamir:
Subtree Isomorphism Revisited. CoRR abs/1510.04622 (2015) - [i5]Amir Abboud, Greg Bodwin:
The 4/3 Additive Spanner Exponent is Tight. CoRR abs/1511.00700 (2015) - [i4]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 abs/1511.06022 (2015) - 2014
- [j1]Daniel Keren, Guy Sagy, Amir Abboud, David Ben-David, Assaf Schuster, Izchak Sharfman, Antonios Deligiannakis:
Geometric Monitoring of Heterogeneous Streams. IEEE Trans. Knowl. Data Eng. 26(8): 1890-1903 (2014) - [c6]Amir Abboud, Kevin Lewi, Ryan Williams:
Losing Weight by Gaining Edges. ESA 2014: 1-12 - [c5]Amir Abboud, Virginia Vassilevska Williams:
Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems. FOCS 2014: 434-443 - [c4]Daniel Keren, Guy Sagy, Amir Abboud, David Ben-David, Assaf Schuster, Izchak Sharfman, Antonios Deligiannakis:
Monitoring Distributed, Heterogeneous Data Streams: The Emergence of Safe Zones. ICAA 2014: 17-28 - [c3]Amir Abboud, Virginia Vassilevska Williams, Oren Weimann:
Consequences of Faster Alignment of Sequences. ICALP (1) 2014: 39-51 - [i3]Amir Abboud, Virginia Vassilevska Williams:
Popular conjectures imply strong lower bounds for dynamic problems. CoRR abs/1402.0054 (2014) - 2013
- [c2]Amir Abboud, Kevin Lewi:
Exact Weight Subgraphs and the k-Sum Conjecture. ICALP (1) 2013: 1-12 - [c1]Daniel Keren, Guy Sagy, Amir Abboud, David Ben-David, Izchak Sharfman, Assaf Schuster:
Safe-Zones for Monitoring Distributed Streams. BD3@VLDB 2013: 7-12 - [i2]Amir Abboud, Kevin Lewi:
Exact Weight Subgraphs and the k-Sum Conjecture. CoRR abs/1304.7558 (2013) - [i1]Amir Abboud, Kevin Lewi, Ryan Williams:
On the parameterized complexity of k-SUM. CoRR abs/1311.3054 (2013)