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

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

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.