research
∙
09/12/2023
The Time Complexity of Fully Sparse Matrix Multiplication
What is the time complexity of matrix multiplication of sparse integer m...
share
research
∙
07/14/2023
On Diameter Approximation in Directed Graphs
Computing the diameter of a graph, i.e. the largest distance, is a funda...
research
∙
05/26/2023
Can You Solve Closest String Faster than Exhaustive Search?
We study the fundamental problem of finding the best string to represent...
research
∙
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 ...
research
∙
11/23/2022
Worst-Case to Expander-Case Reductions
In recent years, the expander decomposition method was used to develop m...
research
∙
11/18/2022
Listing 4-Cycles
In this note we present an algorithm that lists all 4-cycles in a graph ...
research
∙
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...
research
∙
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...
research
∙
03/03/2022
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems
We study several questions related to diversifying search results. We gi...
research
∙
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...
research
∙
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 ...
research
∙
10/29/2021
Friendly Cut Sparsifiers and Faster Gomory-Hu Trees
We devise new cut sparsifiers that are related to the classical sparsifi...
research
∙
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...
research
∙
12/18/2020
Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs
Every undirected graph G has a (weighted) cut-equivalent tree T, commonl...
research
∙
10/27/2020
Impossibility Results for Grammar-Compressed Linear Algebra
To handle vast amounts of data, it is natural and popular to compress ve...
research
∙
09/13/2020
Cut-Equivalent Trees are Optimal for Min-Cut Queries
Min-Cut queries are fundamental: Preprocess an undirected edge-weighted ...
research
∙
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...
research
∙
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 ...
research
∙
02/18/2020
On the Fine-Grained Complexity of Parity Problems
We consider the parity variants of basic problems studied in fine-graine...
research
∙
01/07/2019
Smaller Cuts, Higher Lower Bounds
This paper proves strong lower bounds for distributed computing in the C...
research
∙
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...
research
∙
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...
research
∙
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...
research
∙
04/24/2018
Tighter Connections Between Formula-SAT and Shaving Logs
A noticeable fraction of Algorithms papers in the last few decades impro...
research
∙
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,...
research
∙
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...
research
∙
10/30/2017
