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 …

Parameterized complexity/multivariate complexity algorithmics is an exciting field of modern
algorithm design and analysis, with a broad range of theoretical and practical aspects that …

The goal of this textbook is twofold. First, the book serves as an introduction to the field of
parameterized algorithms and complexity accessible to graduate students and advanced …

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 …

Abstract The Exponential Time Hypothesis (ETH) is a conjecture stating that, roughly
speaking, n-variable 3-SAT cannot be solved in time 2 o (n). In this chapter, we prove lower …

The Fréchet distance is a well-studied and very popular measure of similarity of two curves.
Many variants and extensions have been studied since Alt and Godau introduced this …

The diameter and the radius of a graph are fundamental topological parameters that have
many important practical applications in real world networks. The fastest combinatorial …

We investigate the statistical and computational limits of latent Diffusion Transformers (DiTs)
under the low-dimensional linear latent space assumption. Statistically, we study the …

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 …