Academic Commons

Theses Doctoral

New Methods in Sublinear Computation for High Dimensional Problems

Waingarten, Erik Alex

We study two classes of problems within sublinear algorithms: data structures for approximate nearest neighbor search, and property testing of Boolean functions. We develop algorithmic and analytical tools for proving upper and lower bounds on the complexity of these problems, and obtain the following results:

* We give data structures for approximate nearest neighbor search achieving state-of-the-art approximations for various high-dimensional normed spaces. For example, our data structure for š˜¢š˜³š˜£š˜Ŗš˜µš˜³š˜¢š˜³š˜ŗ normed spaces over Rš˜„ answers queries in sublinear time while using nearly linear space and achieves approximation which is sub-polynomial in the dimension.

* We prove query complexity lower bounds for property testing of three fundamental properties: š˜¬-juntas, monotonicity, and unateness. Our lower bounds for non-adaptive junta testing and adaptive unateness testing are nearly optimal, and the lower bound for adaptive monotonicity testing is the best that is currently known.

* We give an algorithm for testing unateness with nearly optimal query complexity. The algorithm is crucially adaptive and based on a novel analysis of binary search over long paths of the hypercube.


  • thumnail for Waingarten_columbia_0054D_16101.pdf Waingarten_columbia_0054D_16101.pdf application/pdf 2.34 MB Download File

More About This Work

Academic Units
Computer Science
Thesis Advisors
Chen, Xi
Servedio, Rocco Anthony
Ph.D., Columbia University
Published Here
August 3, 2020