AF: Small: Linear and Polynomial Threshold Functions: Structural Analysis and Algorithmic Applications

AF：小：线性和多项式阈值函数：结构分析和算法应用

• 批准号: 1420349
• 负责人: Rocco Servedio
• 金额: $ 45万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-08-01 至 2018-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1420349&HistoricalAwards=false
• 关键词: AF; Small; Linear; Polynomial; Threshold

Consider the commonly occurring situation in which a group of participants each casts a yes-or-no vote and a binary decision is made based on which outcome received the majority of the votes.  This simple scenario arises in countless different settings, from elections involving millions of people to small groups of friends deciding where to go for dinner. A generalization of a simple majority vote is a *weighted* majority voting scheme, in which different participants are allocated different numbers of votes. These weighted voting schemes have many interesting mathematical properties and are present across a wide range of areas, from corporate elections in which larger shareholders have more votes to cast to well-studied models of human neurons (which hold that neurons fire essentially according to a weighted vote of their input signals).  Even more generally, one may consider "higher-order" weighted voting schemes, in which each individual voter may belong to multiple "coalitions", each of which has a weighted vote to cast.In this project, the PI will study weighted majority voting schemes (known as "linear threshold functions" or LTFs) and higher-order generalizations of these schemes (known as "polynomial threshold functions" or PTFs) from a mathematical and computational perspective.  The goal of this study is both to obtain a better understanding of these functions, and to develop improved algorithms for working with these functions in a range of contexts.  Specific problems that the PI will address include: (1) Coming up with new ways to decompose "complex" PTFs into "simpler" PTFs, and to approximate complex PTFs using simpler PTFs.  (2) Developing efficient algorithms that can learn unknown PTFs and LTFs from noisy data, and can construct a desired LTF or PTF to meet a set of "design specifications" such as how much influence different individual voters should have over the final outcome.In terms of broader impacts, an improved understanding of LTFs and PTFs, and more efficient algorithms for working with these fundamental functions, may yield benefits in a range of areas (such as theoretical neuroscience, computer science, voting theory, and more) that use such functions. Other important focuses of the project are to train graduate students through research collaboration, disseminate research results through seminar talks, survey articles and other publications, and to continue ongoing outreach activities aimed at increasing interest in theoretical computer science topics in a broader population, including presentations at elementary schools.

考虑一种常见的情况，即一组参与者各自投赞成票或反对票，并根据哪个结果获得大多数选票来做出二元决策。 这个简单的场景出现在无数不同的场景中，从涉及数百万人的选举到决定去哪里吃饭的小团体朋友。简单多数表决的一般化是 * 加权 * 多数表决方案，其中不同的参与者被分配不同数量的选票。这些加权投票方案具有许多有趣的数学性质，并且存在于广泛的领域，从大股东拥有更多投票权的公司选举到经过充分研究的人类神经元模型（认为神经元基本上根据其输入信号的加权投票而激发）。 甚至更一般地，可以考虑“高阶”加权投票方案，其中每个个体选民可以属于多个“联盟”，每个联盟都有加权投票。PI将研究加权多数表决方案（称为“线性阈值函数”或LTF）和这些计划的高阶推广（称为“多项式阈值函数”或PTF）。 本研究的目标是更好地了解这些功能，并开发改进的算法，在一系列的上下文中使用这些功能。 PI将解决的具体问题包括：（1）提出新的方法将“复杂”的PTF分解为“简单”的PTF，并使用简单的PTF近似复杂的PTF。 (2)开发有效的算法，可以从噪声数据中学习未知的PTF和LTF，并可以构建所需的LTF或PTF，以满足一组“设计规范”，例如不同的个体选民对最终结果的影响程度。就更广泛的影响而言，对LTF和PTF的理解得到改善，以及使用这些基本功能的更有效算法，可能会在使用这些函数的一系列领域（如理论神经科学，计算机科学，投票理论等）中产生好处。该项目的其他重要重点是通过研究合作培训研究生，通过研讨会演讲、调查文章和其他出版物传播研究成果，并继续开展旨在提高更广泛人群对理论计算机科学主题的兴趣的外联活动，包括在小学进行演示。