AF: Small: Threshold Functions--Derandomization, Testing and Applications

University Of Pennsylvania, Philadelphia PA

Investigators

Abstract

Binary classification rules (or Boolean functions) are a standard way to get a single binary (i.e., yes / no) decision from a large number of inputs -- an example is when each voter casts an up / down vote and the outcome is up / down depending on which motion receives a majority of the votes. A slightly more involved example is when the function is not symmetric to all its inputs -- as an example, in the European Union, each country is assigned a different "weight" and a motion passes or fails depending on whether or not the "weighted majority" votes yes or no. Such a classification rule (or Boolean function) is called a linear threshold function (LTF) in mathematics and appears frequently in a diverse range of areas including machine learning, computational complexity theory, electrical engineering, mathematics, voting theory and even neuroscience (where they were first studied as a way to model neurons in the human brain). While simple and intuitive from a definitional point of view, LTFs are sometimes inadequate to model more complicated types of classification rules (useful in areas such as machine learning). In this project, the investigator will study two natural generalizations of LTFs which are significantly more expressive than LTFs and overcome this barrier; on the other hand, their definitional proximity to LTFs make them amenable to rigorous mathematical analysis. Aside from studying these functions through the lens of computational complexity theory, this project will also explore applications of these functions to areas such as machine learning, quantum computing and information theory (i.e., the mathematical theory of communication). The project will train graduate students who will achieve fluency in complexity theory and one or more of these application areas. In addition, several of these topics will also be incorporated in a new graduate course on Boolean functions taught by the investigator at the University of Pennsylvania. The first generalization is a so-called "Polynomial threshold function" (or PTF) which, roughly speaking, allows us to model "higher order effects" (as opposed to LTFs which only allow for "linear effects" of the inputs). The second generalization is a so-called "Intersection of LTFs" which is a Boolean function obtained by applying several LTFs at once. Intersection of LTFs are also a special case of convex bodies, a widely studied object in computer science and mathematics. Jointly referred to as threshold functions, these function classes admit simple geometric interpretations but remain poorly understood from a complexity theoretic point of view. The investigator will study these functions from three distinct vantage points: (i) Derandomization -- i.e., design of efficient deterministic algorithms to compute the probability that a random input satisfies a given threshold function. (ii) Property testing -- i.e., given black-box access to a function, design of an efficient algorithm to test the hypothesis that the given function is a threshold function (either a PTF or an intersection of LTFs). (iii) Harnessing the incredible expressivity of these functions towards applications in information theory and quantum complexity theory. 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.