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

AF：小：阈值函数——去随机化、测试和应用

基本信息

批准号：
1910534
负责人：
Anindya De
金额：
$ 40万
依托单位：
University of Pennsylvania
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-01-01 至 2024-12-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1910534&HistoricalAwards=false
关键词：
AF Small Threshold Functions Derandomization

项目摘要

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.

二元分类规则（或布尔函数）是从大量输入中获得单个二元（即是/否）决策的标准方法 - 一个例子是当每个选民投出赞成/反对票并且结果是向上时/ 下降取决于哪项动议获得多数票。一个稍微复杂一点的例子是，当函数与其所有输入不对称时——例如，在欧盟，每个国家都被分配了不同的“权重”，动议通过或失败取决于“加权”是否多数”投票赞成或反对。这种分类规则（或布尔函数）在数学中被称为线性阈值函数（LTF），经常出现在机器学习、计算复杂性理论、电气工程、数学、投票理论甚至神经科学（其中它们最初被研究作为模拟人脑神经元的方法）。虽然从定义的角度来看，LTF 简单且直观，但有时不足以对更复杂类型的分类规则进行建模（在机器学习等领域很有用）。在这个项目中，研究者将研究 LTF 的两种自然概括，它们比 LTF 更具表达力并克服这一障碍；另一方面，它们在定义上与 LTF 的接近性使得它们能够接受严格的数学分析。除了通过计算复杂性理论的视角研究这些函数之外，该项目还将探索这些函数在机器学习、量子计算和信息论（即通信数学理论）等领域的应用。该项目将培养能够熟练掌握复杂性理论和一个或多个应用领域的研究生。此外，其中几个主题也将纳入宾夕法尼亚大学研究人员教授的新的布尔函数研究生课程中。第一个概括是所谓的“多项式阈值函数”（或 PTF），粗略地说，它允许我们对“高阶效应”进行建模（与仅允许输入的“线性效应”的 LTF 相对）。第二个概括是所谓的“LTF 交集”，它是通过一次应用多个 LTF 获得的布尔函数。 LTF 的交集也是凸体的特例，凸体是计算机科学和数学中广泛研究的对象。这些函数类统称为阈值函数，允许简单的几何解释，但从复杂性理论的角度来看仍然知之甚少。研究者将从三个不同的角度研究这些函数：（i）去随机化——即设计有效的确定性算法来计算随机输入满足给定阈值函数的概率。 (ii) 属性测试——即，给定对函数的黑盒访问，设计一个有效的算法来测试给定函数是阈值函数（PTF 或 LTF 的交集）的假设。 (iii) 利用这些函数令人难以置信的表现力在信息论和量子复杂性理论中的应用。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。