AF: Medium: Collaborative Research: Circuit Lower Bounds via Projections
AF:中:协作研究:通过投影确定电路下界
基本信息
- 批准号:1563155
- 负责人:
- 金额:$ 84.15万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Continuing Grant
- 财政年份:2016
- 资助国家:美国
- 起止时间:2016-04-01 至 2022-03-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Computers play a central role in how we work, play, and communicate with each other in today's world. It is a truism that computers have grown steadily more powerful over the years, but equally important (if not more so) than the amount of sheer computing power available is how efficiently we are able to harness that power. Finding an efficient strategy to solve a given problem (in the language of computer science, an efficient algorithm) can often spell the difference between success and failure. (As an illustrative analogy, consider the task of assembling a large jigsaw puzzle. A poor choice of strategy such as a brute-force approach of trying each pair of pieces against each other may be infeasibly slow, while a cleverer approach such as grouping pieces by their color can be radically more efficient and lead to a feasible solution.) But in order to fully understand the abilities of efficient algorithms, it is crucial to also understand their limits: what is it that efficient algorithms *cannot* do? The field of "computational complexity", which is the subject of the PIs' project, seeks to mathematically prove that certain computational problems do not admit *any* efficient algorithm no matter how long and hard we try to develop one. Such results can have both practical value (by guiding algorithm development away from "dead ends") and deep theoretical significance, as they play a profound role in shaping our fundamental understanding of the phenomenon of computation.The 1980s witnessed exciting progress on a range of Boolean circuit models (a mathematical abstraction of the digital circuits that modern computers are built from) in computational complexity; researchers succeeded in proving many lower bounds establishing that various computational problems have no efficient algorithms in these models. However, further progress slowed significantly after the 1980s. Many of the landmark results obtained in this era were based on the "method of random restrictions", which roughly speaking uses probabilistic arguments to show that Boolean circuits can be dramatically simplified by making certain random substitutions of constant values for input variables. In this project the PIs will intensively investigate an extension of the method of random restrictions which they call the "method of random projections." Rather than simply substituting constant values for input variables, the random projection method additionally identifies groups of variables, "projecting" them all to the same new variable so that they must all take the same value. While the underlying idea is simple, it turns out that this identification of variables helps "maintain useful structure" which is extremely useful for proving lower bounds. In recent work the PIs have successfully used this new "method of random projections" to solve several decades-old problems in Boolean circuit lower bounds and related areas (which in some cases had notoriously resisted progress since the 1980s or 1990s). As the main intellectual goals of the project, the PIs will continue to develop and apply the method of random projections to attack important open problems in Boolean circuit complexity.In addition to the technical goals described above, other central goals of the project are to educate, communicate, and inspire. The PIs will train graduate students through research collaboration, disseminate research results through seminar talks, survey articles and other publications, and continue ongoing outreach activities aimed at increasing interest in and awareness of theoretical computer science topics in a broader population, including presentations at elementary schools.
在当今世界,计算机在我们的工作、娱乐和相互交流中发挥着核心作用。多年来,计算机的功能越来越强大,这是一个不言而喻的事实,但与可用的纯粹计算能力的数量同样重要(如果不是更重要的话)的是,我们能够如何有效地利用这种能力。找到一种有效的策略来解决给定的问题(用计算机科学的语言来说,就是一种有效的算法),往往意味着成功与失败的区别。(作为一个说明性的类比,考虑一下组装一个大型拼图的任务。一个糟糕的策略选择,如尝试每一对棋子相互对抗的暴力方法,可能会非常缓慢,而一个更聪明的方法,如根据棋子的颜色分组,可能会更有效,并导致一个可行的解决方案。)但是为了充分理解高效算法的能力,理解它们的局限性也是至关重要的:高效算法“不能”做什么?“计算复杂性”领域是pi项目的主题,旨在从数学上证明某些计算问题不允许“任何”有效的算法,无论我们努力开发多长时间。这样的结果既具有实用价值(通过引导算法发展远离“死胡同”),又具有深刻的理论意义,因为它们在塑造我们对计算现象的基本理解方面发挥了深远的作用。20世纪80年代,一系列布尔电路模型(构建现代计算机的数字电路的数学抽象)在计算复杂性方面取得了令人兴奋的进展;研究人员成功地证明了许多下界,建立了各种计算问题在这些模型中没有有效的算法。然而,在1980年代以后,进一步的进展明显减缓。在这个时代获得的许多具有里程碑意义的结果都是基于“随机限制方法”,该方法大致上使用概率参数来表明,通过对输入变量进行某些恒定值的随机替换,可以极大地简化布尔电路。在这个项目中,pi将深入研究随机限制方法的扩展,他们称之为“随机投影方法”。随机投影方法不是简单地用常量替换输入变量,而是另外识别变量组,将它们全部“投影”到相同的新变量,以便它们都必须具有相同的值。虽然基本思想很简单,但事实证明,这种变量识别有助于“保持有用的结构”,这对于证明下界非常有用。在最近的工作中,pi成功地使用了这种新的“随机投影方法”来解决布尔电路下界和相关领域中存在了几十年的问题(在某些情况下,自20世纪80年代或90年代以来,这些问题一直阻碍着进展)。作为该项目的主要智力目标,pi将继续发展和应用随机投影方法来解决布尔电路复杂性中的重要开放问题。除了上面描述的技术目标之外,项目的其他中心目标是教育、交流和激励。pi将通过研究合作培训研究生,通过研讨会演讲、调查文章和其他出版物传播研究成果,并继续开展旨在提高更广泛人群对理论计算机科学主题的兴趣和认识的持续外展活动,包括在小学进行演讲。
项目成果
期刊论文数量(1)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
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
{{
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
- 资助金额:
$ 84.15万 - 项目类别:
Continuing Grant
AF: Medium: The Trace Reconstruction Problem
AF:中:迹线重建问题
- 批准号:
2106429 - 财政年份:2021
- 资助金额:
$ 84.15万 - 项目类别:
Continuing Grant
NSF QCIS-FF: Columbia University Computer Science Department Proposal
NSF QCIS-FF:哥伦比亚大学计算机科学系提案
- 批准号:
1926524 - 财政年份:2020
- 资助金额:
$ 84.15万 - 项目类别:
Continuing Grant
Student Travel Grant for 2019 Conference on Computational Complexity (CCC)
2019 年计算复杂性会议 (CCC) 学生旅费补助
- 批准号:
1919026 - 财政年份:2019
- 资助金额:
$ 84.15万 - 项目类别:
Standard Grant
BIGDATA: F: Big Data Analysis via Non-Standard Property Testing
BIGDATA:F:通过非标准属性测试进行大数据分析
- 批准号:
1838154 - 财政年份:2019
- 资助金额:
$ 84.15万 - 项目类别:
Standard Grant
AF: Small: Collaborative Research: Boolean Function Analysis Meets Stochastic Design
AF:小型:协作研究:布尔函数分析与随机设计的结合
- 批准号:
1814873 - 财政年份:2018
- 资助金额:
$ 84.15万 - 项目类别:
Standard Grant
Student Travel Support for CCC 2018
CCC 2018 学生旅行支持
- 批准号:
1822097 - 财政年份:2018
- 资助金额:
$ 84.15万 - 项目类别:
Standard Grant
AF: Student Travel to CCC 2017
AF:2017 年 CCC 学生旅行
- 批准号:
1724073 - 财政年份:2017
- 资助金额:
$ 84.15万 - 项目类别:
Standard Grant
AF: Small: Linear and Polynomial Threshold Functions: Structural Analysis and Algorithmic Applications
AF:小:线性和多项式阈值函数:结构分析和算法应用
- 批准号:
1420349 - 财政年份:2014
- 资助金额:
$ 84.15万 - 项目类别:
Standard Grant
AF: Small: Learning and Testing Classes of Distributions
AF:小:学习和测试分布类
- 批准号:
1319788 - 财政年份:2013
- 资助金额:
$ 84.15万 - 项目类别:
Standard Grant
相似海外基金
Collaborative Research: AF: Medium: The Communication Cost of Distributed Computation
合作研究:AF:媒介:分布式计算的通信成本
- 批准号:
2402836 - 财政年份:2024
- 资助金额:
$ 84.15万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Medium: Foundations of Oblivious Reconfigurable Networks
合作研究:AF:媒介:遗忘可重构网络的基础
- 批准号:
2402851 - 财政年份:2024
- 资助金额:
$ 84.15万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Medium: Algorithms Meet Machine Learning: Mitigating Uncertainty in Optimization
协作研究:AF:媒介:算法遇见机器学习:减轻优化中的不确定性
- 批准号:
2422926 - 财政年份:2024
- 资助金额:
$ 84.15万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Medium: Fast Combinatorial Algorithms for (Dynamic) Matchings and Shortest Paths
合作研究:AF:中:(动态)匹配和最短路径的快速组合算法
- 批准号:
2402283 - 财政年份:2024
- 资助金额:
$ 84.15万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Medium: Foundations of Oblivious Reconfigurable Networks
合作研究:AF:媒介:遗忘可重构网络的基础
- 批准号:
2402852 - 财政年份:2024
- 资助金额:
$ 84.15万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Medium: Fast Combinatorial Algorithms for (Dynamic) Matchings and Shortest Paths
合作研究:AF:中:(动态)匹配和最短路径的快速组合算法
- 批准号:
2402284 - 财政年份:2024
- 资助金额:
$ 84.15万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Medium: The Communication Cost of Distributed Computation
合作研究:AF:媒介:分布式计算的通信成本
- 批准号:
2402837 - 财政年份:2024
- 资助金额:
$ 84.15万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Medium: The Communication Cost of Distributed Computation
合作研究:AF:媒介:分布式计算的通信成本
- 批准号:
2402835 - 财政年份:2024
- 资助金额:
$ 84.15万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Medium: Adventures in Flatland: Algorithms for Modern Memories
合作研究:AF:媒介:平地历险记:现代记忆算法
- 批准号:
2423105 - 财政年份:2024
- 资助金额:
$ 84.15万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Medium: Sketching for privacy and privacy for sketching
合作研究:AF:中:为隐私而素描和为素描而隐私
- 批准号:
2311649 - 财政年份:2023
- 资助金额:
$ 84.15万 - 项目类别:
Continuing Grant