Amir Abboud

Orcid: 0000-0002-0502-4517

According to our database1, Amir Abboud authored at least 67 papers between 2013 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

On csauthors.net:

Bibliography

2024
Reachability Preservers: New Extremal Bounds and Approximation Algorithms.
SIAM J. Comput., 2024

Faster Combinatorial k-Clique Algorithms.
Proceedings of the LATIN 2024: Theoretical Informatics, 2024

2023
Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter.
ACM Trans. Algorithms, January, 2023

New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms.
Electron. Colloquium Comput. Complex., 2023

The Time Complexity of Fully Sparse Matrix Multiplication.
CoRR, 2023

Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

On the Fine-Grained Complexity of Approximating <i>k</i>-Center in Sparse Graphs.
Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Worst-Case to Expander-Case Reductions.
Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Listing 4-Cycles.
Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

What Else Can Voronoi Diagrams Do for Diameter in Planar Graphs?
Proceedings of the 31st Annual European Symposium on Algorithms, 2023

Can You Solve Closest String Faster Than Exhaustive Search?
Proceedings of the 31st Annual European Symposium on Algorithms, 2023

On Diameter Approximation in Directed Graphs.
Proceedings of the 31st Annual European Symposium on Algorithms, 2023

On Complexity of 1-Center in Various Metrics.
Proceedings of the Approximation, 2023

2022
SETH-based Lower Bounds for Subset Sum and Bicriteria Path.
ACM Trans. Algorithms, 2022

Scheduling lower bounds via AND subset sum.
J. Comput. Syst. Sci., 2022

Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond.
Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Friendly Cut Sparsifiers and Faster Gomory-Hu Trees.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems.
Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time.
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs.
Theory Comput., 2021

Smaller Cuts, Higher Lower Bounds.
ACM Trans. Algorithms, 2021

Gomory-Hu Tree in Subcubic Time.
CoRR, 2021

Subcubic algorithms for Gomory-Hu tree in unweighted graphs.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Fine-Grained Hardness for Edit Distance to a Fixed Sequence.
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time.
Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020
Fooling views: a new lower bound technique for distributed computations under congestion.
Distributed Comput., 2020

New hardness results for planar graph problems in p and an algorithm for sparsest cut.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Impossibility Results for Grammar-Compressed Linear Algebra.
Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

On the Fine-Grained Complexity of Parity Problems.
Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Cut-Equivalent Trees are Optimal for Min-Cut Queries.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019
Dynamic set cover: improved algorithms and lower bounds.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Subquadratic High-Dimensional Hierarchical Clustering.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Evaluation of intel 3D-xpoint NVDIMM technology for memory-intensive genomic workloads.
Proceedings of the International Symposium on Memory Systems, 2019

Faster Algorithms for All-Pairs Bounded Min-Cuts.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018
Subtree Isomorphism Revisited.
ACM Trans. Algorithms, 2018

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture.
SIAM J. Comput., 2018

If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser.
SIAM J. Comput., 2018

A Hierarchy of Lower Bounds for Sublinear Additive Spanners.
SIAM J. Comput., 2018

More consequences of falsifying SETH and the orthogonal vectors conjecture.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Near-Optimal Compression for the Planar Graph Metric.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Tighter Connections Between Formula-SAT and Shaving Logs.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017
Hardness in P.
PhD thesis, 2017

The 4/3 Additive Spanner Exponent Is Tight.
J. ACM, 2017

Distributed PCP Theorems for Hardness of Approximation in P.
CoRR, 2017

Towards Hardness of Approximation for Polynomial Time Problems.
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Distributed PCP Theorems for Hardness of Approximation in P.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016
Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks.
Proceedings of the Distributed Computing - 30th International Symposium, 2016

Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Error Amplification for Pairwise Spanner Lower Bounds.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter.
CoRR, 2015

Quadratic-Time Hardness of LCS and other Sequence Similarity Measures.
CoRR, 2015

More Applications of the Polynomial Method to Algorithm Design.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Tight Hardness Results for LCS and Other Sequence Similarity Measures.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014
Geometric Monitoring of Heterogeneous Streams.
IEEE Trans. Knowl. Data Eng., 2014

Consequences of Faster Alignment of Sequences.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Monitoring Distributed, Heterogeneous Data Streams: The Emergence of Safe Zones.
Proceedings of the Applied Algorithms - First International Conference, 2014

Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

Losing Weight by Gaining Edges.
Proceedings of the Algorithms - ESA 2014, 2014

2013
On the parameterized complexity of k-SUM.
CoRR, 2013

Safe-Zones for Monitoring Distributed Streams.
Proceedings of the First International Workshop on Big Dynamic Distributed Data, 2013

Exact Weight Subgraphs and the k-Sum Conjecture.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013


  Loading...