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

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

• 批准号: 1814873
• 负责人: Rocco Servedio
• 金额: $ 16.63万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-06-01 至 2022-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1814873&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 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Learning Sums of Independent Random Variables with Sparse Collective Support

在稀疏集体支持下学习独立随机变量的和

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

Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces

从少量迹线重建近乎最优的平均情况近似迹线

• DOI: 1.9781611977073.34
• 发表时间: 2022-01
• 期刊: Proceedings of the annual ACMSIAM symposium on discrete algorithms
• 作者: Chen, Xi;De, Anindya;Lee, Chin Ho;Servedio, Rocco A.;Sinha, Sandip
• 通讯作者: Sinha, Sandip

Beyond Trace Reconstruction: Population Recovery from the Deletion Channel

超越痕迹重建：从删除通道中恢复种群

• DOI: 10.1109/focs.2019.00050
• 发表时间: 2019-11
• 期刊: Proceedings of the IEEE 60th Annual Symposium on Foundations of Computer Science
• 作者: Ban, Frank;Chen, Xi;Freilich, Adam;Servedio, Rocco A.;Sinha, Sandip
• 通讯作者: Sinha, Sandip

Polynomial-time trace reconstruction in the smoothed complexity model

平滑复杂度模型中的多项式时间迹重建

• DOI: 10.1137/1.9781611976465.5
• 发表时间: 2021-01
• 期刊: Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
• 作者: Chen, Xi;De, Anindya;Lee, Chin Ho;Servedio, Rocco A.;Sinha, Sandip
• 通讯作者: Sinha, Sandip

Density Estimation for Shift-Invariant Multidimensional Distributions

平移不变多维分布的密度估计

• DOI: 10.4230/lipics.itcs.2019.28
• 发表时间: 2019-01
• 期刊: Innovations in Theoretical Computer Science
• 作者: De, Anindya;Long, Philip;Servedio, Rocco
• 通讯作者: Servedio, Rocco