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/14/2023
On Diameter Approximation in Directed Graphs
Computing the diameter of a graph, i.e. the largest distance, is a funda...
research
∙
11/10/2022
A New Conjecture on Hardness of Low-Degree 2-CSP's with Implications to Hardness of Densest k-Subgraph and Other Problems
We propose a new conjecture on hardness of low-degree 2-CSP's, and show ...
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
∙
06/10/2021
Hardness of Approximate Diameter: Now for Undirected Graphs
Approximating the graph diameter is a basic task of both theoretical and...
research
∙
06/03/2021
Approximation Algorithms for Min-Distance Problems in DAGs
The min-distance between two nodes u, v is defined as the minimum of the...
research
∙
11/10/2020
Distributed Distance Approximation
Diameter, radius and eccentricities are fundamental graph parameters, wh...
research
∙
11/08/2020
Tight Conditional Lower Bounds for Approximating Diameter in Directed Graphs
Among the most fundamental graph parameters is the Diameter, the largest...
research
∙
08/14/2020
New Techniques for Proving Fine-Grained Average-Case Hardness
The recent emergence of fine-grained cryptography strongly motivates dev...
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
∙
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
