research
∙
12/17/2020
Sampling Arborescences in Parallel
We study the problem of sampling a uniformly random directed rooted span...
share
research
∙
11/04/2020
Algorithms and Hardness for Linear Algebra on Geometric Graphs
For a function 𝖪 : ℝ^d×ℝ^d→ℝ_≥ 0, and a set P = { x_1, …, x_n}⊂ℝ^d of n ...
research
∙
06/27/2019
Improved Distributed Approximation to Maximum Independent Set
We present improved results for approximating Maximum Independent Set ()...
research
∙
04/05/2019
Network design for s-t effective resistance
We consider a new problem of designing a network with small s-t effectiv...
research
∙
01/21/2019
A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs
The Capacitated Vehicle Routing problem is to find a minimum-cost set of...
research
∙
12/01/2018
Semi-Online Bipartite Matching
In this paper we introduce the semi-online model that generalizes the cl...
research
∙
11/27/2018
A Schur Complement Cheeger Inequality
Cheeger's inequality shows that any undirected graph G with minimum nonz...
research
∙
10/07/2018
Spectral Subspace Sparsification
We introduce a new approach to spectral sparsification that approximates...
research
∙
11/17/2017
