AF: Small: Collaborative Research: Boolean Function Analysis Meets Stochastic Design
AF:小型:协作研究:布尔函数分析与随机设计的结合
基本信息
- 批准号:1814873
- 负责人:
- 金额:$ 16.63万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2018
- 资助国家:美国
- 起止时间:2018-06-01 至 2022-05-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)在只提供部分资料的情况下,何时及在多大程度上可以重建?该奖项反映了美国国家科学基金会的法定使命,并通过使用基金会的知识价值和更广泛的影响审查标准进行评估,被认为值得支持。
项目成果
期刊论文数量(5)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
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
Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces
从少量迹线重建近乎最优的平均情况近似迹线
- DOI:
- 发表时间:2022
- 期刊:
- 影响因子:0
- 作者: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
- 期刊:
- 影响因子:0
- 作者: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
- 期刊:
- 影响因子:0
- 作者:De, Anindya;Long, Philip;Servedio, Rocco
- 通讯作者:Servedio, Rocco
{{
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 }}
Rocco Servedio其他文献
Theory of Computing
计算理论
- DOI:
10.4086/toc - 发表时间:
2013 - 期刊:
- 影响因子:0
- 作者:
Alexandr Andoni;Nikhil Bansal;P. Beame;Giuseppe Italiano;Sanjeev Khanna;Ryan O’Donnell;T. Pitassi;T. Rabin;Tim Roughgarden;Clifford Stein;Rocco Servedio;Amir Abboud;Nima Anari;Ibm Srinivasan Arunachalam;T. J. Watson;Research Center;Petra Berenbrink;Aaron Bernstein;Aditya Bhaskara;Sayan Bhattacharya;Eric Blais;H. Bodlaender;Adam Bouland;Anne Broadbent;Mark Bun;Timothy Chan;Arkadev Chattopadhyay;Xue Chen;Gil Cohen;Dana Dachman;Anindya De;Shahar Dobzhinski;Zhiyi Huang;Ken;Robin Kothari;Marvin Künnemann;Tu Kaiserslautern;Rasmus Kyng;E. Zurich;Sophie Laplante;D. Lokshtanov;S. Mahabadi;Nicole Megow;Ankur Moitra;Technion Shay Moran;Google Research;Christopher Musco;Prasad Raghavendra;Alex Russell;Laura Sanità;Alex Slivkins;David Steurer;Epfl Ola Svensson;Chaitanya Swamy;Madhur Tulsiani;Christos Tzamos;Andreas Wiese;Mary Wootters;Huacheng Yu;Aaron Potechin;Aaron Sidford;Aarushi Goel;Aayush Jain;Abhiram Natarajan;Abhishek Shetty;Adam Karczmarz;Adam O’Neill;Aditi Dudeja;Aditi Laddha;Aditya Krishnan;Adrian Vladu Afrouz;J. Ameli;Ainesh Bakshi;Akihito Soeda;Akshay Krishnamurthy;Albert Cheu;A. Grilo;Alex Wein;Alexander Belov;Alexander Block;Alexander Golovnev;Alexander Poremba;Alexander Shen;Alexander Skopalik;Alexandra Henzinger;Alexandros Hollender;Ali Parviz;Alkis Kalavasis;Allen Liu;Aloni Cohen;Amartya Shankha;Biswas Amey;Bhangale Amin;Coja;Yehudayoff Amir;Zandieh Amit;Daniely Amit;Kumar Amnon;Ta;Beimel Anand;Louis Anand Natarajan;Anders Claesson;André Chailloux;André Nusser;Andrea Coladangelo;Andrea Lincoln;Andreas Björklund;Andreas Maggiori;A. Krokhin;A. Romashchenko;Andrej Risteski;Anirban Chowdhury;Anirudh Krishna;A. Mukherjee;Ankit Garg;Anna Karlin;Anthony Leverrier;Antonio Blanca;A. Antoniadis;Anupam Gupta;Anupam Prakash;A. Singh;Aravindan Vijayaraghavan;Argyrios Deligkas;Ariel Kulik;Ariel Schvartzman;Ariel Shaulker;A. Cornelissen;Arka Rai;Choudhuri Arkady;Yerukhimovich Arnab;Bhattacharyya Arthur Mehta;Artur Czumaj;A. Backurs;A. Jambulapati;Ashley Montanaro;A. Sah;A. Mantri;Aviad Rubinstein;Avishay Tal;Badih Ghazi;Bartek Blaszczyszyn;Benjamin Moseley;Benny Pinkas;Bento Natura;Bernhard Haeupler;Bill Fefferman;B. Mance;Binghui Peng;Bingkai Lin;B. Sinaimeri;Bo Waggoner;Bodo Manthey;Bohdan Kivva;Brendan Lucier Bundit;Laekhanukit Burak;Sahinoglu Cameron;Seth Chaodong Zheng;Charles Carlson;Chen;Chenghao Guo;Chenglin Fan;Chenwei Wu;Chethan Kamath;Chi Jin;J. Thaler;Jyun;Kaave Hosseini;Kaito Fujii;Kamesh Munagala;Kangning Wang;Kanstantsin Pashkovich;Karl Bringmann Karol;Wegrzycki Karteek;Sreenivasaiah Karthik;Chandrasekaran Karthik;Sankararaman Karthik;C. S. K. Green;Larsen Kasturi;Varadarajan Keita;Xagawa Kent Quanrud;Kevin Schewior;Kevin Tian;Kilian Risse;Kirankumar Shiragur;K. Pruhs;K. Efremenko;Konstantin Makarychev;Konstantin Zabarnyi;Krišj¯anis Pr¯usis;Kuan Cheng;Kuikui Liu;Kunal Marwaha;Lars Rohwedder László;Kozma László;A. Végh;L'eo Colisson;Leo de Castro;Leonid Barenboim Letong;Li;Li;L. Roditty;Lieven De;Lathauwer Lijie;Chen Lior;Eldar Lior;Rotem Luca Zanetti;Luisa Sinisclachi;Luke Postle;Luowen Qian;Lydia Zakynthinou;Mahbod Majid;Makrand Sinha;Malin Rau Manas;Jyoti Kashyop;Manolis Zampetakis;Maoyuan Song;Marc Roth;Marc Vinyals;Marcin Bieńkowski;Marcin Pilipczuk;Marco Molinaro;Marcus Michelen;Mark de Berg;M. Jerrum;Mark Sellke;Mark Zhandry;Markus Bläser;Markus Lohrey;Marshall Ball;Marthe Bonamy;Martin Fürer;Martin Hoefer;M. Kokainis;Masahiro Hachimori;Matteo Castiglioni;Matthias Englert;Matti Karppa;Max Hahn;Max Hopkins;Maximilian Probst;Gutenberg Mayank Goswami;Mehtaab Sawhney;Meike Hatzel;Meng He;Mengxiao Zhang;Meni Sadigurski;M. Parter;M. Dinitz;Michael Elkin;Michael Kapralov;Michael Kearns;James R. Lee;Sudatta Bhattacharya;Michal Koucký;Hadley Black;Deeparnab Chakrabarty;C. Seshadhri;Mahsa Derakhshan;Naveen Durvasula;Nika Haghtalab;Peter Kiss;Thatchaphol Saranurak;Soheil Behnezhad;M. Roghani;Hung Le;Shay Solomon;Václav Rozhon;Anders Martinsson;Christoph Grunau;G. Z. —. Eth;Zurich;Switzerland;Morris Yau — Massachusetts;Noah Golowich;Dhruv Rohatgi — Massachusetts;Qinghua Liu;Praneeth Netrapalli;Csaba Szepesvári;Debarati Das;Jacob Gilbert;Mohammadtaghi Hajiaghayi;Tomasz Kociumaka;B. Saha;K. Bringmann;Nick Fischer — Weizmann;Ce Jin;Yinzhan Xu — Massachusetts;Virginia Vassilevska Williams;Yinzhan Xu;Josh Alman;Kevin Rao;Hamed Hatami;—. XiangMeng;McGill University;Edith Cohen;Xin Lyu;Tamás Jelani Nelson;Uri Stemmer — Google;Research;Daniel Alabi;Pravesh K. Kothari;Pranay Tankala;Prayaag Venkat;Fred Zhang;Samuel B. Hopkins;Gautam Kamath;Shyam Narayanan — Massachusetts;Marco Gaboardi;R. Impagliazzo;Rex Lei;Satchit Sivakumar;Jessica Sorrell;T. Korhonen;Marco Bressan;Matthias Lanzinger;Huck Bennett;Mahdi Cheraghchi;V. Guruswami;João Ribeiro;Jan Dreier;Nikolas Mählmann;Sebastian Siebertz — TU Wien;The Randomized k ;Conjecture Is;False;Sébastien Bubeck;Christian Coester;Yuval Rabani — Microsoft;Wei;Ethan Mook;Daniel Wichs;Joshua Brakensiek;Sai Sandeep — Stanford;University;Lorenzo Ciardo;Stanislav Živný;Amey Bhangale;Subhash Khot;Dor Minzer;David Ellis;Guy Kindler;Noam Lifshitz;Ronen Eldan;Dan Mikulincer;George Christodoulou;E. Koutsoupias;Annamária Kovács;José Correa;Andrés Cristi;Xi Chen;Matheus Venturyne;Xavier Ferreira;David C. Parkes;Yang Cai;Jinzhao Wu;Zhengyang Liu;Zeyu Ren;Zihe Wang;Ravishankar Krishnaswamy;Shi Li;Varun Suriyanarayana - 通讯作者:
Varun Suriyanarayana
Rocco Servedio的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Rocco Servedio', 18)}}的其他基金
Collaborative Research: AF: Medium: Continuous Concrete Complexity
合作研究:AF:中:连续混凝土复杂性
- 批准号:
2211238 - 财政年份:2022
- 资助金额:
$ 16.63万 - 项目类别:
Continuing Grant
AF: Medium: The Trace Reconstruction Problem
AF:中:迹线重建问题
- 批准号:
2106429 - 财政年份:2021
- 资助金额:
$ 16.63万 - 项目类别:
Continuing Grant
NSF QCIS-FF: Columbia University Computer Science Department Proposal
NSF QCIS-FF:哥伦比亚大学计算机科学系提案
- 批准号:
1926524 - 财政年份:2020
- 资助金额:
$ 16.63万 - 项目类别:
Continuing Grant
Student Travel Grant for 2019 Conference on Computational Complexity (CCC)
2019 年计算复杂性会议 (CCC) 学生旅费补助
- 批准号:
1919026 - 财政年份:2019
- 资助金额:
$ 16.63万 - 项目类别:
Standard Grant
BIGDATA: F: Big Data Analysis via Non-Standard Property Testing
BIGDATA:F:通过非标准属性测试进行大数据分析
- 批准号:
1838154 - 财政年份:2019
- 资助金额:
$ 16.63万 - 项目类别:
Standard Grant
Student Travel Support for CCC 2018
CCC 2018 学生旅行支持
- 批准号:
1822097 - 财政年份:2018
- 资助金额:
$ 16.63万 - 项目类别:
Standard Grant
AF: Student Travel to CCC 2017
AF:2017 年 CCC 学生旅行
- 批准号:
1724073 - 财政年份:2017
- 资助金额:
$ 16.63万 - 项目类别:
Standard Grant
AF: Medium: Collaborative Research: Circuit Lower Bounds via Projections
AF:中:协作研究:通过投影确定电路下界
- 批准号:
1563155 - 财政年份:2016
- 资助金额:
$ 16.63万 - 项目类别:
Continuing Grant
AF: Small: Linear and Polynomial Threshold Functions: Structural Analysis and Algorithmic Applications
AF:小:线性和多项式阈值函数:结构分析和算法应用
- 批准号:
1420349 - 财政年份:2014
- 资助金额:
$ 16.63万 - 项目类别:
Standard Grant
AF: Small: Learning and Testing Classes of Distributions
AF:小:学习和测试分布类
- 批准号:
1319788 - 财政年份:2013
- 资助金额:
$ 16.63万 - 项目类别:
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 RNAs在克罗恩病发生发展中的功能和作用机制
- 批准号:31870821
- 批准年份:2018
- 资助金额:56.0 万元
- 项目类别:面上项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
- 批准号:31802058
- 批准年份:2018
- 资助金额:26.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
- 资助金额:
$ 16.63万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Exploring the Frontiers of Adversarial Robustness
合作研究:AF:小型:探索对抗鲁棒性的前沿
- 批准号:
2335411 - 财政年份:2024
- 资助金额:
$ 16.63万 - 项目类别:
Standard Grant
NSF-BSF: Collaborative Research: AF: Small: Algorithmic Performance through History Independence
NSF-BSF:协作研究:AF:小型:通过历史独立性实现算法性能
- 批准号:
2420942 - 财政年份:2024
- 资助金额:
$ 16.63万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
- 批准号:
2347322 - 财政年份:2024
- 资助金额:
$ 16.63万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Real Solutions of Polynomial Systems
合作研究:AF:小:多项式系统的实数解
- 批准号:
2331401 - 财政年份:2024
- 资助金额:
$ 16.63万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Real Solutions of Polynomial Systems
合作研究:AF:小:多项式系统的实数解
- 批准号:
2331400 - 财政年份:2024
- 资助金额:
$ 16.63万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: New Connections between Optimization and Property Testing
合作研究:AF:小型:优化和性能测试之间的新联系
- 批准号:
2402572 - 财政年份:2024
- 资助金额:
$ 16.63万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: New Directions in Algorithmic Replicability
合作研究:AF:小:算法可复制性的新方向
- 批准号:
2342245 - 财政年份:2024
- 资助金额:
$ 16.63万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
- 批准号:
2347321 - 财政年份:2024
- 资助金额:
$ 16.63万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: New Connections between Optimization and Property Testing
合作研究:AF:小型:优化和性能测试之间的新联系
- 批准号:
2402571 - 财政年份:2024
- 资助金额:
$ 16.63万 - 项目类别:
Standard Grant