2025 Theses Doctoral

Data Structure Frameworks for Optimization and Search

Jiang, Shunhua

Many important theoretical and practical problems can be solved using continuous optimization. As data generation continues to grow at an unprecedented rate, there is a growing need for the most efficient possible algorithms, particularly those that achieve optimal or nearly input-size complexity. This thesis focuses on developing theoretical results for faster and nearly-optimal optimization and search algorithms through the use of data structures.

The first part of this thesis presents faster algorithms for fundamental optimization problems including linear programming (LP), semidefinite programming (SDP), sum-of-squares optimization (SOS), and 𝓁_∞ regression. We show how specialized data structures can reduce the cost per iteration in iterative optimization algorithms, leading to faster solvers for these problems.

The second part of this thesis covers our work on data structures for several fundamental online problems including dynamic 𝓁₂ regression and partial match. For the partial match problem, we developed a general framework for building data structures by simulating communication protocols, which is also applicable to other online search problems.