AF: Small : Collaborative Research : A Theory of High Dimensional Property Testing

University Of California-Santa Cruz, Santa Cruz CA

Investigators

Abstract

The advent of massive data sets requires the design and analysis of algorithms accessing only a tiny portion of input data. This proposal aims to further the mathematical study of these algorithms in the context of sublinear algorithms and property testing within theoretical computer science. Specifically, the focus is an in-depth understanding of data represented as high dimensional functions, a paradigm prevalent in many optimization problems, and how useful properties of these can be quickly ascertained using small samples. An understanding of these issues foreseeably will lead to better, faster, and more robust algorithms for data analysis. The proposal involves training and mentoring graduate and undergraduate students at the investigators' respective institutions with special attention given to women and minority students. The findings of this proposal will be made accessible to public not only via technical reports but also via blogs and videos accessible to everyone. The investigators have a track record of converting theoretical understandings to practical algorithms, and this proposal will continue this effort. Discrete, high dimensional functions are ubiquitous in science, and it is imperative to understand and exploit properties of these functions. Many fundamental properties such as monotonicity, Lipschitz continuity, convexity and submodularity are defined by bounds on the first, second, or higher derivatives of these functions. This proposal aims to understand the theory behind derivative-bounded property testing, and in particular discover the fastest algorithms that determine whether a function (approximately) satisfies a property from this class. In particular, the proposal aims to achieve the following goals: (1) Obtain a fast tester of submodularity and discrete convexity, building on previous work of the investigators on first derivative testers. (2) Transfer results from discrete settings to continuous settings, and obtain testers for properties like convexity. (3) Uncover more connections between geometric concepts like duality and isoperimetry with derivative testing algorithms, as has been suggested by previous work of the investigators. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.