research
∙
07/29/2023
Listing Cliques from Smaller Cliques
We study finding and listing k-cliques in a graph, for constant k≥ 3, a ...
share
research
∙
07/16/2023
New Bounds for Matrix Multiplication: from Alpha to Omega
The main contribution of this paper is a new improved variant of the las...
research
∙
03/25/2023
Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More
In this paper we carefully combine Fredman's trick [SICOMP'76] and Matou...
research
∙
02/24/2023
Optimal Bounds for Noisy Sorting
Sorting is a fundamental problem in computer science. In the classical s...
research
∙
12/29/2022
Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules
We present an almost optimal algorithm for the classic Chamberlin-Couran...
research
∙
11/14/2022
Removing Additive Structure in 3SUM-Based Reductions
Our work explores the hardness of 3SUM instances without certain additiv...
research
∙
09/15/2022
Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failures
This paper considers a natural fault-tolerant shortest paths problem: fo...
research
∙
04/22/2022
Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds
The AP-LCA problem asks, given an n-node directed acyclic graph (DAG), t...
research
∙
04/05/2022
All-Pairs Shortest Path Distances with Differential Privacy: Improved Algorithms for Bounded and Unbounded Weights
We revisit the problem of privately releasing the all-pairs shortest pat...
research
∙
03/16/2022
Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV
The 3SUM hypothesis, the APSP hypothesis and SETH are the three main hyp...
research
∙
02/23/2022
Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv
The main theme of this paper is using k-dimensional generalizations of t...
research
∙
05/06/2021
Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths
One of the most basic graph problems, All-Pairs Shortest Paths (APSP) is...
research
∙
03/05/2021
Fine-Grained Complexity and Algorithms for the Schulze Voting Method
We study computational aspects of a well-known single-winner voting rule...
research
∙
02/11/2021
Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths
APSP with small integer weights in undirected graphs [Seidel'95, Galil a...
research
∙
07/18/2020
Monochromatic Triangles, Triangle Listing and APSP
One of the main hypotheses in fine-grained complexity is that All-Pairs ...
research
∙
04/19/2020
Faster Dynamic Range Mode
In the dynamic range mode problem, we are given a sequence a of length b...
research
∙
10/10/2019
Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications
The goal of this paper is to get truly subcubic algorithms for Min-Plus ...
research
∙
04/25/2019
Approximation Algorithms for Min-Distance Problems
We study fundamental graph parameters such as the Diameter and Radius in...
research
∙
04/18/2018
Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures
Since the introduction of retroactive data structures at SODA 2004, a ma...
research
∙
01/23/2018