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)在只提供部分资料的情况下，何时及在多大程度上可以重建？该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

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