We present a general framework of designing efficient dynamic approximate algorithms for
optimization problems on undirected graphs. In particular, we develop a technique that …

Lipschitz extensions were proposed as a tool for designing differentially private algorithms
for approximating graph statistics. However, efficiently computable Lipschitz extensions …

We survey problems, results, ideas, and recent progress in the Ribe program. The goal of
this research program, which is motivated by a classical rigidity theorem of Martin Ribe, is to …

We study dynamic algorithms for maintaining spectral vertex sparsifiers of graphs with
respect to a set of terminals T of our choice. Such objects preserve pairwise resistances …

For undirected graphs $ G=(V, E) $ and $ G_0=(V_0, E_0) $, say that $ G $ is a region
intersection graph over $ G_0 $ if there is a family of connected subsets $\{R_u\subseteq …

We study graph partitioning problems from a min-max perspective, in which an input graph
on n vertices should be partitioned into k parts, and the objective is to minimize the …

We study vertex sparsification for distances, in the setting of planar graphs with distortion:
Given a planar graph G (with edge weights) and a subset of k terminal vertices, the goal is to …

We present a fast construction algorithm for the hierarchical tree decompositions that lie at
the heart of oblivious routing strategies and that form the basis for approximation and online …

A partition of a weighted graph is-sparse if every cluster has diameter at most, and every ball
of radius intersects at most clusters. Similarly, is-scattering if instead for balls, we require that …

Given a capacitated graph G=(V,E) and a set of terminals K⊆V, how should we produce a
graph H only on the terminals K so that every (multicommodity) flow between the terminals in …