In recent years, a new “fine-grained” theory of computational hardness has been developed,
based on “fine-grained reductions” that focus on exact running times for problems …

We consider several well-studied problems in dynamic algorithms and prove that sufficient
progress on any of them would imply a breakthrough on one of five major open problems in …

The radius and diameter are fundamental graph parameters, with several natural definitions
for directed graphs. Each definition is well-motivated in a variety of applications. All versions …

Algorithmic research strives to develop fast algorithms for fundamental problems. Despite its
many successes, however, many problems still do not have very efficient algorithms. For …

Measuring the importance of a node in a network is a major goal in the analysis of social
networks, biological systems, transportation networks etc. Different centrality measures have …

We present a new technique for efficiently removing almost all short cycles in a graph
without unintentionally removing its triangles. Consequently, triangle finding problems do …

We present a new distributed model of probabilistically checkable proofs (PCP). A satisfying
assignment x∈{0, 1} n to a CNF formula φ is shared between two parties, where Alice …

We develop a new technique for constructing sparse graphs that allow us to prove near-
linear lower bounds on the round complexity of computing distances in the CONGEST …

We design fast deterministic algorithms for distance computation in the CONGESTED
CLIQUE model. Our key contributions include: A (2+ ε)-approximation for all-pairs shortest …

Among the most important graph parameters is the Diameter, the largest distance between
any two vertices. There are no known very efficient algorithms for computing the Diameter …