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
• 期刊: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: Anindya De;Philip M. Long;R. Servedio

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

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

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

Polynomial-time trace reconstruction in the smoothed complexity model

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

• DOI: 10.1137/1.9781611976465.5
• 发表时间: 2021
• 期刊: 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
• 期刊: Innovations in Theoretical Computer Science
• 作者: De, Anindya;Long, Philip;Servedio, Rocco
• 通讯作者: Servedio, Rocco