Exploiting Additive Structure in Algorithm Design and Fine-Grained Complexity

Abstract

In this thesis, we investigate the fine-grained complexity of various algorithmic problems with an additive flavor, including 3SUM, Subset Sum, and their close relatives. We explore their connections to various areas, such as graph algorithms, discrete optimization, combinatorial pattern matching, and computational geometry. Our new results include improved algorithms and conditional lower bounds for a wide range of problems, answering multiple open questions from the literature:

• Conditional lower bounds for graph problems: We prove new lower bounds for 4-Cycle Listing and Approximate Distance Oracles conditioned on the 3SUM Hypothesis. As a key intermediate step, we show a fine-grained reduction from 3SUM to the special case of 3SUM where all pairwise sums of input numbers are distinct.

• Combinatorial pattern matching: We design improved algorithms for Text-to-Pattern Hamming Distances, Pattern Matching with Wildcards, and Geometric Pattern Matching, by drawing connections from 3SUM and sparse convolution.

• Knapsack-type problems: We obtain a pseudo-polynomial time algorithm for 0-1 Knapsack with (conditionally) near-optimal dependence on the maximum item weight, an improved approximation scheme for the counting problem #Knapsack, and improved exponential time algorithms for the total search problem Pigeonhole Equal Subset Sum.

In order to obtain these results, we employ and develop techniques based on convolution algorithms and their extensions, as well as classic tools from additive combinatorics.