AF: Small: Collaborative Research: Boolean Function Analysis Meets Stochastic Design
AF:小:协作研究:布尔函数分析与随机设计的结合
基本信息
- 批准号:1926872
- 负责人:
- 金额:$ 28.45万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2019
- 资助国家:美国
- 起止时间:2019-01-01 至 2023-01-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
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的法定使命,并通过使用基金会的智力价值和更广泛的影响审查标准进行评估,被认为值得支持。
项目成果
期刊论文数量(16)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Junta Correlation is Testable
- DOI:10.1109/focs.2019.00090
- 发表时间:2019-04
- 期刊:
- 影响因子:0
- 作者:Anindya De;Elchanan Mossel;Joe Neeman
- 通讯作者:Anindya De;Elchanan Mossel;Joe Neeman
Reconstructing weighted voting schemes from partial information about their power indices
根据权力指数的部分信息重建加权投票方案
- DOI:
- 发表时间:2021
- 期刊:
- 影响因子:0
- 作者:Bennett, Huck;De, Anindya;Servedio, Rocco A.;Vlatakis-Gkaragkounis, Emmanouil V.
- 通讯作者:Vlatakis-Gkaragkounis, Emmanouil V.
Simple and efficient pseudorandom genera- tors from Gaussian processes.
来自高斯过程的简单高效的伪随机生成器。
- DOI:
- 发表时间:2019
- 期刊:
- 影响因子:0
- 作者:Chattopadhyay, Eshan;De, Anindya;Servedio, Rocco
- 通讯作者:Servedio, Rocco
Reconstructing Ultrametric Trees from Noisy Experiments
从嘈杂的实验中重建超度量树
- DOI:
- 发表时间:2023
- 期刊:
- 影响因子:0
- 作者:Arunachaleswaran, Eshwar R.;De, Anindya;Kannan, Sampath
- 通讯作者:Kannan, Sampath
Learning Sums of Independent Random Variables with Sparse Collective Support
- DOI:10.1109/focs.2018.00036
- 发表时间:2018-07
- 期刊:
- 影响因子:0
- 作者:Anindya De;Philip M. Long;R. Servedio
- 通讯作者:Anindya De;Philip M. Long;R. Servedio
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Anindya De其他文献
Noise Stability is computable and low dimensional
噪声稳定性是可计算的且低维的
- DOI:
- 发表时间:
2017 - 期刊:
- 影响因子:0
- 作者:
Anindya De;Elchanan Mossel;Joe Neeman - 通讯作者:
Joe Neeman
Time Space Tradeoffs for Attacks against One-Way Functions and PRGs
针对单向函数和 PRG 的攻击的时空权衡
- DOI:
- 发表时间:
2010 - 期刊:
- 影响因子:0
- 作者:
Anindya De;L. Trevisan;Madhur Tulsiani - 通讯作者:
Madhur Tulsiani
Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries
布尔函数单调性测试需要(几乎)n 1/2 个非自适应查询
- DOI:
- 发表时间:
2014 - 期刊:
- 影响因子:0
- 作者:
Xi Chen;Anindya De;R. Servedio;Li - 通讯作者:
Li
Dealing with Inaccurate Measures of Size in Two-Stage Probability Proportional to Size Sample Designs: Applications in African Household Surveys
处理与规模样本设计成比例的两阶段概率中不准确的规模测量:在非洲家庭调查中的应用
- DOI:
10.1093/jssam/smaa020 - 发表时间:
2020 - 期刊:
- 影响因子:2.1
- 作者:
G. Kalton;I. F. Cervantes;Carlos Arieira;Mike Kwanisai;E. Radin;S. Saito;Anindya De;Stephen McCracken;P. Stupp - 通讯作者:
P. Stupp
Efficient deterministic approximate counting for low-degree polynomial threshold functions
低次多项式阈值函数的高效确定性近似计数
- DOI:
10.1145/2591796.2591800 - 发表时间:
2013 - 期刊:
- 影响因子:0
- 作者:
Anindya De;Rocco A. Servedio - 通讯作者:
Rocco A. Servedio
Anindya De的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Anindya De', 18)}}的其他基金
CAREER: Learning and property testing -- a complexity theoretic perspective
职业:学习和属性测试——复杂性理论的视角
- 批准号:
2045128 - 财政年份:2021
- 资助金额:
$ 28.45万 - 项目类别:
Continuing Grant
AF: Small: Threshold Functions--Derandomization, Testing and Applications
AF:小:阈值函数——去随机化、测试和应用
- 批准号:
1910534 - 财政年份:2020
- 资助金额:
$ 28.45万 - 项目类别:
Standard Grant
AF: Small: Collaborative Research: Boolean Function Analysis Meets Stochastic Design
AF:小型:协作研究:布尔函数分析与随机设计的结合
- 批准号:
1814706 - 财政年份:2018
- 资助金额:
$ 28.45万 - 项目类别:
Standard Grant
相似国自然基金
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
- 批准号:
- 批准年份:2024
- 资助金额:0.0 万元
- 项目类别:省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
- 批准号:n/a
- 批准年份:2022
- 资助金额:10.0 万元
- 项目类别:省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
- 批准号:32000033
- 批准年份:2020
- 资助金额:24.0 万元
- 项目类别:青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
- 批准号:31972324
- 批准年份:2019
- 资助金额:58.0 万元
- 项目类别:面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
- 批准号:81900988
- 批准年份:2019
- 资助金额:21.0 万元
- 项目类别:青年科学基金项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
- 批准号:31802058
- 批准年份:2018
- 资助金额:26.0 万元
- 项目类别:青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
- 批准号:31870821
- 批准年份:2018
- 资助金额:56.0 万元
- 项目类别:面上项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
- 批准号:31772128
- 批准年份:2017
- 资助金额:60.0 万元
- 项目类别:面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
- 批准号:81704176
- 批准年份:2017
- 资助金额:20.0 万元
- 项目类别:青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
- 批准号:91640114
- 批准年份:2016
- 资助金额:85.0 万元
- 项目类别:重大研究计划
相似海外基金
Collaborative Research: AF: Small: New Directions in Algorithmic Replicability
合作研究:AF:小:算法可复制性的新方向
- 批准号:
2342244 - 财政年份:2024
- 资助金额:
$ 28.45万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Exploring the Frontiers of Adversarial Robustness
合作研究:AF:小型:探索对抗鲁棒性的前沿
- 批准号:
2335411 - 财政年份:2024
- 资助金额:
$ 28.45万 - 项目类别:
Standard Grant
NSF-BSF: Collaborative Research: AF: Small: Algorithmic Performance through History Independence
NSF-BSF:协作研究:AF:小型:通过历史独立性实现算法性能
- 批准号:
2420942 - 财政年份:2024
- 资助金额:
$ 28.45万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
- 批准号:
2347322 - 财政年份:2024
- 资助金额:
$ 28.45万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Real Solutions of Polynomial Systems
合作研究:AF:小:多项式系统的实数解
- 批准号:
2331401 - 财政年份:2024
- 资助金额:
$ 28.45万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Real Solutions of Polynomial Systems
合作研究:AF:小:多项式系统的实数解
- 批准号:
2331400 - 财政年份:2024
- 资助金额:
$ 28.45万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: New Connections between Optimization and Property Testing
合作研究:AF:小型:优化和性能测试之间的新联系
- 批准号:
2402572 - 财政年份:2024
- 资助金额:
$ 28.45万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: New Directions in Algorithmic Replicability
合作研究:AF:小:算法可复制性的新方向
- 批准号:
2342245 - 财政年份:2024
- 资助金额:
$ 28.45万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
- 批准号:
2347321 - 财政年份:2024
- 资助金额:
$ 28.45万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: New Connections between Optimization and Property Testing
合作研究:AF:小型:优化和性能测试之间的新联系
- 批准号:
2402571 - 财政年份:2024
- 资助金额:
$ 28.45万 - 项目类别:
Standard Grant