research
∙
08/16/2023
Approximating Min-Diameter: Standard and Bichromatic
The min-diameter of a directed graph G is a measure of the largest dista...
share
research
∙
07/29/2023
Listing Cliques from Smaller Cliques
We study finding and listing k-cliques in a graph, for constant k≥ 3, a ...
research
∙
07/18/2023
Fast 2-Approximate All-Pairs Shortest Paths
In this paper, we revisit the classic approximate All-Pairs Shortest Pat...
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
∙
07/14/2023
On Diameter Approximation in Directed Graphs
Computing the diameter of a graph, i.e. the largest distance, is a funda...
research
∙
07/04/2023
Faster Detours in Undirected Graphs
The k-Detour problem is a basic path-finding problem: given a graph G on...
research
∙
06/19/2023
Quasipolynomiality of the Smallest Missing Induced Subgraph
We study the problem of finding the smallest graph that does not occur a...
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
∙
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
∙
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
∙
09/05/2022
Induced Cycles and Paths Are Harder Than You Think
The goal of the paper is to give fine-grained hardness results for the S...
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/06/2022
Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles
We study the approximability of two related problems: n-Pairs Shortest P...
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
∙
12/13/2021
Isometric Hamming embeddings of weighted graphs
A mapping α : V(G) → V(H) from the vertex set of one graph G to another ...
research
∙
12/13/2021
Factorization and pseudofactorization of weighted graphs
For unweighted graphs, finding isometric embeddings is closely related t...
research
∙
10/29/2021
Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product
We obtain improved lower bounds for additive spanners, additive emulator...
research
∙
06/10/2021
Hardness of Approximate Diameter: Now for Undirected Graphs
Approximating the graph diameter is a basic task of both theoretical and...
research
∙
05/07/2021
Improved Approximation for Longest Common Subsequence over Small Alphabets
This paper investigates the approximability of the Longest Common Subseq...
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/11/2021
Hardness of Token Swapping on Trees
Given a graph where every vertex has exactly one labeled token, how can ...
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
∙
11/10/2020
Distributed Distance Approximation
Diameter, radius and eccentricities are fundamental graph parameters, wh...
research
∙
10/20/2020
New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners
Maintaining and updating shortest paths information in a graph is a fund...
research
∙
10/12/2020
A Refined Laser Method and Faster Matrix Multiplication
The complexity of matrix multiplication is measured in terms of ω, the s...
research
∙
09/30/2020
Monochromatic Triangles, Intermediate Matrix Products, and Convolutions
The most studied linear algebraic operation, matrix multiplication, has ...
research
∙
08/14/2020
New Techniques for Proving Fine-Grained Average-Case Hardness
The recent emergence of fine-grained cryptography strongly motivates dev...
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/23/2020
Conditionally optimal approximation algorithms for the girth of a directed graph
It is known that a better than 2-approximation algorithm for the girth i...
research
∙
04/23/2020
Directed Girth
It is known that a better than 2-approximation algorithm for the girth i...
research
∙
01/29/2020
New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs
In the dynamic Single-Source Shortest Paths (SSSP) problem, we are given...
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
∙
08/30/2019
Equivalences between triangle and range query problems
We define a natural class of range query problems, and prove that all pr...
research
∙
04/25/2019
Approximation Algorithms for Min-Distance Problems
We study fundamental graph parameters such as the Diameter and Radius in...
research
∙
04/25/2019
Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
Some of the most fundamental and well-studied graph parameters are the D...
research
∙
04/07/2019
Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles
We consider the pattern detection problem in graphs: given a constant si...
research
∙
11/29/2018
Algorithms and Hardness for Diameter in Dynamic Graphs
The diameter, radius and eccentricities are natural graph parameters. Wh...
research
∙
10/19/2018
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
We study the known techniques for designing Matrix Multiplication algori...
research
∙
08/26/2018
Towards Tight Approximation Bounds for Graph Diameter and Eccentricities
Among the most important graph parameters is the Diameter, the largest d...
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
∙
12/21/2017
Tight Hardness for Shortest Cycles and Paths in Sparse Graphs
Fine-grained reductions have established equivalences between many core ...
research
∙
12/19/2017
Further limitations of the known approaches for matrix multiplication
We consider the techniques behind the current best algorithms for matrix...
research
∙
11/21/2017
Fine-Grained I/O Complexity via Reductions: New lower bounds, faster algorithms, and a time hierarchy
This paper initiates the study of I/O algorithms (minimizing cache misse...
research
∙
07/02/2017