research
∙
04/18/2023
Parallel Greedy Spanners
A t-spanner of a graph is a subgraph that t-approximates pairwise distan...
share
research
∙
03/22/2023
Almost-Optimal Sublinear Additive Spanners
Given an undirected unweighted graph G = (V, E) on n vertices and m edge...
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
∙
11/07/2022
Query Complexity of the Metric Steiner Tree Problem
We study the query complexity of the metric Steiner Tree problem, where ...
research
∙
06/21/2022
Near-Linear ε-Emulators for Planar Graphs
We study vertex sparsification for distances, in the setting of planar g...
research
∙
03/28/2022
Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics
We consider the design of sublinear space and query complexity algorithm...
research
∙
02/14/2022
A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs
We consider the classical Minimum Crossing Number problem: given an n-ve...
research
∙
07/12/2021
Worst-Case Welfare of Item Pricing in the Tollbooth Problem
We study the worst-case welfare of item pricing in the tollbooth problem...
research
∙
11/12/2020
Towards Better Approximation of Graph Crossing Number
Graph Crossing Number is a fundamental problem with various applications...
research
∙
06/12/2020
On Packing Low-Diameter Spanning Trees
Edge connectivity of a graph is one of the most fundamental graph-theore...
research
∙
05/05/2020
The Expander Hierarchy and its Applications to Dynamic Graph Algorithms
We introduce a notion for hierarchical graph clustering which we call th...
research
∙
01/23/2019