PhD Defense

1. Knapsack: The Knapsack problem is a classic combinatorial optimization problem. We give a collection of improved exact and approximation algorithms for Knapsack and some of its variants. Our study is guided by the connection between Knapsack and min-plus convolution, a central problem in fine-grained complexity.

2. Sublinear Edit Distance: The edit distance is a popular and practically motivated measure of similarity between texts. We focus on sublinear-time algorithms, which aim to approximate the edit distance 𝑘 of two texts without reading them entirely. Our main result is a 𝑘^𝑜(1)-approximation in time 𝑂(𝑛/𝑘 + 𝑘^{2+𝑜(1)}). This constitutes a quadratic improvement over the previous state of the art, and matches an unconditional lower bound for small k (up to subpolynomial factors in the running time and approximation factor).

3. Negative Weight Single-Source Shortest Paths: Computing shortest paths from a source in a weighted directed graph is a fundamental problem. When all edge weights are nonnegative, the classic Dijkstra’s algorithm solves this problem in near-linear time. It has been a long-standing open question to obtain a near-linear time algorithm when the graph contains negative edge weights. This has been solved recently in a breakthrough by Bernstein, Nanongkai and Wulff-Nilsen, who presented an algorithm in time 𝑂(𝑚 log^8 𝑛 log𝑊 ). Our contribution is an improvement by nearly 6 log factors.