AF: Small: Collaborative Research: Boolean Function Analysis Meets Stochastic Design

AF：小：协作研究：布尔函数分析与随机设计的结合

• 批准号: 1926872
• 负责人: Anindya De
• 金额: $ 28.45万
• 依托单位: University of Pennsylvania
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-01-01 至 2023-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1926872&HistoricalAwards=false
• 关键词: AF; Small; Collaborative; Research; Boolean

A central goal in the field of optimization is to develop effective procedures for decision-making in the presence of constraints. These constraints are often imposed by real-world data, but it is frequently the case that the relevant data is not completely known to the agent performing the optimization; it is natural to model such settings using probability distributions associated with the data. In such analyses, the constraints associated with the optimization problem are now themselves "stochastic," and a standard goal is to maximize the likelihood of satisfying all the constraints while incurring minimum cost. (As a motivating example, an airline may wish to operate as few flights as possible while ensuring that with 99% probability, no passenger is bumped.) Apart from modeling uncertainty, optimization with stochastic constraints also provides a way to succinctly model constraints whose standard description is very large; design problems in voting theory, where there are very many voters, are examples of this kind. This project studies both of these kinds of problems, called stochastic design problems, from a unified new perspective based on techniques from computational complexity theory. The project also trains graduate students who will achieve fluency both in complexity theory and in optimization, and will promote cross-disciplinary activities between operations research and theoretical computer science. The motivating insight which underlies this project is that Boolean function analysis -- a topic at the intersection of harmonic analysis, probability theory, and complexity theory -- provides a useful suite of techniques for stochastic design problems. The investigators will study two broad topics. The first one is on chance-constrained optimization: In problems of this sort, one is given a set of stochastic constraints and the aim is to satisfy all the constraints with at least a certain fixed threshold probability. While previous work on such problems has typically achieved computationally efficient algorithms by relaxing the actual set of constraints, the investigators will focus on algorithms which exactly satisfy the original given set of stochastic constraints. This line of work will address the chance-constrained versions of fundamental optimization problems such as bin packing, knapsack, and linear programming. The second broad topic is that of inverse problems in social choice theory: Game theorists use so-called "power indices" to measure the influence of voters in voting schemes. A basic algorithmic problem is to design efficient algorithms for the inverse problem, in which, given a set of prescribed power indices, the goal is to construct a voting game with these indices. The investigators will study questions such as (a) to what extent is a given voting scheme specified by its power indices? (b) what is the complexity of exactly reconstructing an unknown target voting game given its power indices? (c) when and to what extent is reconstruction possible in a partial information setting?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.

优化领域的一个核心目标是在存在约束的情况下制定有效的决策程序。这些约束通常是由现实世界数据施加的，但是通常情况下，执行优化的代理并不完全知道相关数据。使用与数据关联的概率分布来对此设置进行建模是很自然的。在此类分析中，与优化问题相关的约束本身就是“随机”，一个标准目标是最大程度地提高满足所有约束的可能性，同时产生最低成本。 （作为一个激励人物的例子，一家航空公司可能希望尽可能少的飞行，同时确保有99％的概率，没有乘客碰撞。投票理论中有很多选民的设计问题就是这种例子。 该项目从统一的新角度研究了基于计算复杂性理论的技术，研究了这两种问题，称为随机设计问题。该项目还培训研究生，他们将在复杂性理论和优化方面都能达到流利，并将促进运营研究与理论计算机科学之间的跨学科活动。 该项目构成的激励洞察力是，布尔函数分析 - 谐波分析，概率理论和复杂性理论的主题为随机设计问题提供了有用的技术套件。研究人员将研究两个广泛的主题。第一个是对机会约束的优化：在这种问题中，给出了一组随机约束，目的是满足所有约束，至少具有一定的固定阈值概率。尽管以前在此类问题上的工作通常通过放松实际约束来实现计算有效算法，但研究人员将专注于完全满足原始给定的随机约束集的算法。这项工作将解决基本优化问题的机会约束版本，例如垃圾箱包装，背包和线性编程。第二个广泛的话题是社会选择理论中的反问题：游戏理论家使用所谓的“权力指数”来衡量选民在投票方案中的影响。一个基本的算法问题是为反问题设计有效的算法，在该算法中，鉴于一组规定的权力指数，目标是用这些索引构建一个投票游戏。调查人员将研究（a）其权力指数指定的给定投票方案等问题？ （b）鉴于其功率指数，确切重建未知目标投票游戏的复杂性是什么？ （c）在部分信息设置中何时何地重建？该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛的影响审查标准通过评估来获得支持的。

项目成果

Junta Correlation is Testable

• DOI: 10.1109/focs.2019.00090
• 发表时间: 2019-04
• 期刊: 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: Anindya De;Elchanan Mossel;Joe Neeman

Reconstructing Ultrametric Trees from Noisy Experiments

从嘈杂的实验中重建超度量树

• 发表时间: 2023
• 期刊: Proceedings of Machine Learning Research
• 作者: Arunachaleswaran, Eshwar R.;De, Anindya;Kannan, Sampath
• 通讯作者: Kannan, Sampath

Reconstructing weighted voting schemes from partial information about their power indices

根据权力指数的部分信息重建加权投票方案

• 发表时间: 2021
• 期刊: Proceedings of Thirty Fourth Conference on Learning Theory
• 作者: Bennett, Huck;De, Anindya;Servedio, Rocco A.;Vlatakis-Gkaragkounis, Emmanouil V.
• 通讯作者: Vlatakis-Gkaragkounis, Emmanouil V.

Reconstruction under outliers for Fourier-sparse functions

傅里叶稀疏函数异常值下的重建

• DOI: 10.1137/1.9781611975994.124
• 发表时间: 2020
• 期刊: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms
• 作者: Chen, Xue;De, Anindya
• 通讯作者: De, Anindya

Learning Sums of Independent Random Variables with Sparse Collective Support

• DOI: 10.1109/focs.2018.00036
• 发表时间: 2018-07
• 期刊: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: Anindya De;Philip M. Long;R. Servedio