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。 (2) 开发有效的算法，可以从噪声数据中学习未知的 PTF 和 LTF，并可以构建所需的 LTF 或 PTF 以满足一组“设计规范”，例如不同个体选民对最终结果应有多大影响。就更广泛的影响而言，加深对 LTF 和 PTF 的理解，以及使用这些基本功能的更有效的算法，可能会在一系列领域（例如理论神经科学、计算机科学、投票理论等）产生好处该项目的其他重要重点是通过研究合作培训研究生，通过研讨会演讲、调查文章和其他出版物传播研究成果，并继续开展旨在提高人们对理论计算机科学主题的兴趣的外展活动。更广泛的人群，包括在小学的演讲。