Amir Abboud | DeepAI

AI Chat

Featured Co-authors

Pasin Manurangsi
58 publications
Jason Li
55 publications
Robert Krauthgamer
51 publications
Thatchaphol Saranurak
49 publications
Karl Bringmann
49 publications
Virginia Vassilevska Williams
45 publications
Vincent Cohen-Addad
45 publications
Euiwoong Lee
30 publications
Debmalya Panigrahi
29 publications
Keren Censor-Hillel
28 publications
Jesper Nederlof
25 publications

∙ 09/12/2023

The Time Complexity of Fully Sparse Matrix Multiplication

What is the time complexity of matrix multiplication of sparse integer m...

0 Amir Abboud, et al. ∙

∙ 07/14/2023

On Diameter Approximation in Directed Graphs

Computing the diameter of a graph, i.e. the largest distance, is a funda...

0 Amir Abboud, et al. ∙

∙ 05/26/2023

Can You Solve Closest String Faster than Exhaustive Search?

We study the fundamental problem of finding the best string to represent...

0 Amir Abboud, et al. ∙

∙ 05/04/2023

What Else Can Voronoi Diagrams Do For Diameter In Planar Graphs?

The Voronoi diagrams technique was introduced by Cabello to compute the ...

0 Amir Abboud, et al. ∙

∙ 11/23/2022

Worst-Case to Expander-Case Reductions

In recent years, the expander decomposition method was used to develop m...

0 Amir Abboud, et al. ∙

∙ 11/18/2022

Listing 4-Cycles

In this note we present an algorithm that lists all 4-cycles in a graph ...

0 Amir Abboud, et al. ∙

∙ 11/14/2022

Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics

The "short cycle removal" technique was recently introduced by Abboud, B...

0 Amir Abboud, et al. ∙

∙ 04/22/2022

Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond

We present a new technique for efficiently removing almost all short cyc...

0 Amir Abboud, et al. ∙

∙ 03/03/2022

Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems

We study several questions related to diversifying search results. We gi...

0 Amir Abboud, et al. ∙

∙ 12/06/2021

On Complexity of 1-Center in Various Metrics

We consider the classic 1-center problem: Given a set P of n points in a...

0 Amir Abboud, et al. ∙

∙ 11/09/2021

Gomory-Hu Tree in Subcubic Time

In 1961, Gomory and Hu showed that the max-flow values of all n 2 pairs ...

0 Amir Abboud, et al. ∙

∙ 10/29/2021

Friendly Cut Sparsifiers and Faster Gomory-Hu Trees

We devise new cut sparsifiers that are related to the classical sparsifi...

0 Amir Abboud, et al. ∙

∙ 06/05/2021

APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time

We design an n^2+o(1)-time algorithm that constructs a cut-equivalent (G...

0 Amir Abboud, et al. ∙

∙ 12/18/2020

Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs

Every undirected graph G has a (weighted) cut-equivalent tree T, commonl...

0 Amir Abboud, et al. ∙

∙ 10/27/2020

Impossibility Results for Grammar-Compressed Linear Algebra

To handle vast amounts of data, it is natural and popular to compress ve...

0 Amir Abboud, et al. ∙

∙ 09/13/2020

Cut-Equivalent Trees are Optimal for Min-Cut Queries

Min-Cut queries are fundamental: Preprocess an undirected edge-weighted ...

0 Amir Abboud, et al. ∙

∙ 07/05/2020

New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut

The Sparsest Cut is a fundamental optimization problem that has been ext...

0 Amir Abboud, et al. ∙

∙ 03/16/2020

Scheduling Lower Bounds via AND Subset Sum

Given N instances (X_1,t_1),...,(X_N,t_N) of Subset Sum, the AND Subset ...

0 Amir Abboud, et al. ∙

∙ 02/18/2020

On the Fine-Grained Complexity of Parity Problems

We consider the parity variants of basic problems studied in fine-graine...

0 Amir Abboud, et al. ∙

∙ 01/07/2019

Smaller Cuts, Higher Lower Bounds

This paper proves strong lower bounds for distributed computing in the C...

0 Amir Abboud, et al. ∙

∙ 01/05/2019

New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs

We investigate the time-complexity of the All-Pairs Max-Flow problem: Gi...

0 Amir Abboud, et al. ∙

∙ 07/16/2018

Faster Algorithms for All-Pairs Bounded Min-Cuts

Given a directed graph, the vertex connectivity from u to v is the maxim...

0 Amir Abboud, et al. ∙

∙ 05/22/2018

More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture

The Strong Exponential Time Hypothesis and the OV-conjecture are two pop...

0 Amir Abboud, et al. ∙

∙ 04/24/2018

Tighter Connections Between Formula-SAT and Shaving Logs

A noticeable fraction of Algorithms papers in the last few decades impro...

0 Amir Abboud, et al. ∙

∙ 03/02/2018

Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve

Can we analyze data without decompressing it? As our data keeps growing,...

0 Amir Abboud, et al. ∙

∙ 11/05/2017

Fooling Views: A New Lower Bound Technique for Distributed Computations under Congestion

We introduce a novel lower bound technique for distributed graph algorit...

0 Amir Abboud, et al. ∙

∙ 10/30/2017

Reachability Preservers: New Extremal Bounds and Approximation Algorithms

In this paper we prove new results about the extremal structure of paths...

0 Amir Abboud, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world