Collaborative Research: AF: Medium: Continuous Concrete Complexity

点击翻译按钮获取中文摘要

In theoretical computer science the well-established field of concrete complexity studies structural properties of "Boolean functions", which are decision rules that amalgamate a list of responses to yes/no questions to produce a single yes/no output value. Boolean functions are central to many branches of computer science, including the study of machine-learning algorithms (where a major goal is to efficiently infer Boolean functions based on their input-output performance) as well as hyperefficient "property testing" algorithms that inspect only a tiny portion of a massive data set in order to estimate some global property of the data. In a parallel, but to-date largely disconnected, line of research, mathematicians have expended great effort towards understanding structural properties of various types of geometric sets in high-dimensional continuous space. Such sets can also be viewed as "decision rules", but ones that amalgamate a list of continuous numerical values, rather than discrete yes/no answers, in order to produce a yes/no value (which indicates whether or not the input point described by the numerical values belongs to the set). Viewed from this very high-level perspective these two lines of research have similar broad goals, but the techniques they use are quite different, and the two fields have mostly considered distinct types of questions and mathematical objects.In this project the investigators will work to establish and deepen connections between the two settings --- discrete and continuous --- described above. The driving force behind this project is an analogy, developed by the investigators in a sequence of recent works, between Boolean functions that are monotone non-decreasing and high-dimensional sets that are convex. This perspective has already led to a number of surprising new results and suggests a broad range of new notions and questions as well as methods of proof. Building on their preliminary work, the investigators will work to establish new structural results for high-dimensional geometric sets (focusing in particular on convex sets in continuous high-dimensional spaces that are endowed with the Gaussian distribution) that are inspired by analogous structural results that have been established in concrete complexity for Boolean functions. As mentioned above, the structural results obtained to date in concrete complexity for discrete domains have proved very useful for computer science applications such as computational learning, property testing, and derandomization; the investigators will work to establish similar applications in learning, testing, and derandomization in the continuous setting. The investigators will also develop the connection between the discrete and continuous settings in the other direction, by working to apply some of the powerful methods of high-dimensional convex geometry to obtain new structural and algorithmic results in the discrete Boolean setting. Finally, another important goal of the project is to train graduate students through the process of research collaboration and dissemination, with a particular goal of building expertise that spans both the topics of high-dimensional convex geometry and discrete Boolean concrete complexity.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.