AF: Large: Theory of Computation - Pushing the State-of-the-Art
AF:大:计算理论 - 推动最先进的技术
基本信息
- 批准号:1412958
- 负责人:
- 金额:$ 200万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Continuing Grant
- 财政年份:2014
- 资助国家:美国
- 起止时间:2014-09-01 至 2020-08-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
This project is aimed at understanding a variety of fundamental questions in the theory of computation. It will be carried out via the postdoctoral mentoring program at the Institute for Advanced Study, and as such the specific topics of focus will evolve with the postdocs present each year. Current foci include, among others, the following:- The power of formulas. Formulas is the most basic mathematical and computational descriptive mechanisms. Understanding their minimal length for natural problems captures at once limitation on the space requirements, as well as the potential parallelism inherent in the problem. The award will focus on the most challenging direction, which has so far resisted attack - proving limitation of formulas. More generally, the researchers will pursue proving limitations of other natural computational models, especially arithmetic computation.- The power of relaxationsThe "meta-algorithms": Linear and semi-definite relaxations of integer programs, are among the most fruitful and powerful techniques for solving (or finding approximate solutions) to optimization problems. The award will focus on understanding the limits of these techniques. This work ties in naturally to understanding the limitations of natural proof systems and of natural strategies for search algorithms.- Peeking inside the "black-box"One of the most useful paradigms in programming and learning is the encapsulation of objects as black-boxes, to which only input-output access is allowed. With this utility come limitations which can hopefully overcome if we are allowed some access into the internal workings of the black box. Modeling such access, in scientific experiments, machine learning and computational complexity is a challenge the researchers plan to pursue.Computational complexity, a foundational core of computer science, has proved itself a remarkably deep and fruitful fountain of problems, ideas and techniques over the past decades. The research agenda is expected to be a driver of innovation in Theoretical Computer Science and related disciplines. Some of the areas of study have potential implications outside theory, especially machine learning, coding theory, scientific discovery and more. On the educational side, the mentoring program furthers the quality of IAS postdocs to serve as outstanding teachers, graduate advisors and academic leaders and innovators in one of the most exciting branches of science today. Whether IAS alumni pursue a career in academia or industry their impact on technology and on the training of new generations undergraduate and graduate education is immense.
该项目旨在理解计算理论中的各种基本问题。 它将通过高级研究所的博士后指导计划进行,因此,重点的具体主题将随着每年博士后的出现而发展。目前的重点包括,除其他外,以下:-公式的力量。公式是最基本的数学和计算描述机制。理解它们对于自然问题的最小长度,可以立即捕获对空间要求的限制,以及问题固有的潜在并行性。该奖项将集中在最具挑战性的方向,这是迄今为止抵制攻击证明公式的限制。更一般地说,研究人员将继续证明其他自然计算模型的局限性,特别是算术计算。松弛的力量“元算法”:整数规划的线性和半定松弛,是解决(或找到近似解)优化问题的最富有成效和最强大的技术之一。该奖项将侧重于了解这些技术的局限性。这项工作自然地与理解自然证明系统和搜索算法的自然策略的局限性联系在一起。在编程和学习中最有用的范例之一是将对象封装为黑盒,只允许输入输出访问。 有了这个实用程序,如果我们被允许进入黑盒的内部工作,希望可以克服这些限制。 在科学实验、机器学习和计算复杂性中对这种访问进行建模是研究人员计划追求的一项挑战。计算复杂性是计算机科学的基础核心,在过去几十年中,它已经证明了自己是问题、思想和技术的一个非常深刻和富有成效的源泉。 研究议程预计将成为理论计算机科学和相关学科创新的驱动力。一些研究领域具有理论之外的潜在影响,特别是机器学习,编码理论,科学发现等等。在教育方面,辅导计划进一步提高了IAS博士后的质量,使其成为当今最令人兴奋的科学分支之一的优秀教师,研究生导师和学术领袖和创新者。 无论IAS校友追求学术界或工业界的职业生涯,他们对技术和新一代本科生和研究生教育的培训的影响是巨大的。
项目成果
期刊论文数量(4)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Automating cutting planes is NP-hard
自动化切割平面是 NP 困难的
- DOI:10.1145/3357713.3384248
- 发表时间:2020
- 期刊:
- 影响因子:0
- 作者:Göös, M;Koroth, S;Mertz, I;Pitassi, T.
- 通讯作者:Pitassi, T.
Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings
不变环生成元的代数复杂性、GCT 和硬度搜索问题
- DOI:
- 发表时间:2020
- 期刊:
- 影响因子:0
- 作者:Garg, A;Ikenmeyer, C;Makam, V;Oliveira, R;Walter, M;Wigderson, A.
- 通讯作者:Wigderson, A.
AND testing and robust judgement aggregation
AND 测试和稳健的判断聚合
- DOI:10.1145/3357713.3384254
- 发表时间:2020
- 期刊:
- 影响因子:0
- 作者:Filmus, Y;Lifshitz, N;Minzer, D;Mossel, E.
- 通讯作者:Mossel, E.
Geometric rank of tensors and subrank of matrix multiplication
张量的几何秩和矩阵乘法的子秩
- DOI:
- 发表时间:2020
- 期刊:
- 影响因子:0
- 作者:Kopparty, S;Moshkovitz, G;Zuiddam, J.
- 通讯作者:Zuiddam, J.
{{
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 }}
Avi Wigderson其他文献
Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications
使用悲观估计器和应用程序对 Ahlswede-Winter 矩阵值切尔诺夫界限进行去随机化
- DOI:
- 发表时间:
2008 - 期刊:
- 影响因子:1
- 作者:
Avi Wigderson;David Xiao - 通讯作者:
David Xiao
Robust Local Testability of Tensor Products of LDPC Codes
LDPC码张量积的鲁棒局部可测试性
- DOI:
- 发表时间:
2006 - 期刊:
- 影响因子:0
- 作者:
Irit Dinur;Madhu Sudan;Avi Wigderson - 通讯作者:
Avi Wigderson
Electronic Colloquium on Computational Complexity Tiny Families of Functions with Random Properties: a Quality{size Trade{oo for Hashing
关于计算复杂性的电子研讨会具有随机属性的微小函数族:哈希的质量{大小交易{oo
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
O. Goldreich;Avi Wigderson - 通讯作者:
Avi Wigderson
On rank vs. communication complexity
- DOI:
10.1007/bf01192527 - 发表时间:
1995-12-01 - 期刊:
- 影响因子:1.000
- 作者:
Noam Nisan;Avi Wigderson - 通讯作者:
Avi Wigderson
Good permutation codes based on the shuffle-exchange network
- DOI:
10.1007/s11856-023-2498-4 - 发表时间:
2023-10-10 - 期刊:
- 影响因子:0.800
- 作者:
Oded Goldreich;Avi Wigderson - 通讯作者:
Avi Wigderson
Avi Wigderson的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Avi Wigderson', 18)}}的其他基金
AF: Medium: Theory of Computation - New Algorithmic and Hardness Techniques
AF:媒介:计算理论 - 新算法和硬度技术
- 批准号:
1900460 - 财政年份:2019
- 资助金额:
$ 200万 - 项目类别:
Continuing Grant
Lie Groups, Representations and Discrete Mathematics
李群、表示和离散数学
- 批准号:
0542278 - 财政年份:2006
- 资助金额:
$ 200万 - 项目类别:
Standard Grant
ITR Medium Award: Computational Complexity Theory 2003
ITR 中奖:计算复杂性理论 2003
- 批准号:
0324906 - 财政年份:2003
- 资助金额:
$ 200万 - 项目类别:
Continuing Grant
Special Year in Computational Complexity Theory
计算复杂性理论特别年
- 批准号:
9987077 - 财政年份:2000
- 资助金额:
$ 200万 - 项目类别:
Standard Grant
Basic Research in Theoretical Computer Science and Discrete Mathematics
理论计算机科学与离散数学基础研究
- 批准号:
9987845 - 财政年份:2000
- 资助金额:
$ 200万 - 项目类别:
Standard Grant
相似国自然基金
水稻穗粒数调控关键因子LARGE6的分子遗传网络解析
- 批准号:
- 批准年份:2022
- 资助金额:30 万元
- 项目类别:青年科学基金项目
量子自旋液体中拓扑拟粒子的性质:量子蒙特卡罗和新的large-N理论
- 批准号:
- 批准年份:2020
- 资助金额:62 万元
- 项目类别:面上项目
甘蓝型油菜Large Grain基因调控粒重的分子机制研究
- 批准号:31972875
- 批准年份:2019
- 资助金额:58.0 万元
- 项目类别:面上项目
Large PB/PB小鼠 视网膜新生血管模型的研究
- 批准号:30971650
- 批准年份:2009
- 资助金额:8.0 万元
- 项目类别:面上项目
基因discs large在果蝇卵母细胞的后端定位及其体轴极性形成中的作用机制
- 批准号:30800648
- 批准年份:2008
- 资助金额:20.0 万元
- 项目类别:青年科学基金项目
LARGE基因对口腔癌细胞中α-DG糖基化及表达的分子调控
- 批准号:30772435
- 批准年份:2007
- 资助金额:29.0 万元
- 项目类别:面上项目
相似海外基金
CAREER: Learning Theory for Large-scale Stochastic Games
职业:大规模随机博弈的学习理论
- 批准号:
2339240 - 财政年份:2024
- 资助金额:
$ 200万 - 项目类别:
Continuing Grant
Exploring Large-Scale Geometry via Local and Nonlocal Potential Theory
通过局部和非局部势理论探索大尺度几何
- 批准号:
2348748 - 财政年份:2024
- 资助金额:
$ 200万 - 项目类别:
Standard Grant
CIF: Small: Theory and Algorithms for Efficient and Large-Scale Monte Carlo Tree Search
CIF:小型:高效大规模蒙特卡罗树搜索的理论和算法
- 批准号:
2327013 - 财政年份:2023
- 资助金额:
$ 200万 - 项目类别:
Standard Grant
Collaborative Research: CIF: Small: New Theory, Algorithms and Applications for Large-Scale Bilevel Optimization
合作研究:CIF:小型:大规模双层优化的新理论、算法和应用
- 批准号:
2311274 - 财政年份:2023
- 资助金额:
$ 200万 - 项目类别:
Standard Grant
Collaborative Research: CIF: Small: New Theory, Algorithms and Applications for Large-Scale Bilevel Optimization
合作研究:CIF:小型:大规模双层优化的新理论、算法和应用
- 批准号:
2311275 - 财政年份:2023
- 资助金额:
$ 200万 - 项目类别:
Standard Grant
Investigation into the distribution of frictional strength on the plate interface and the large-thrust earthquake occurrence by seismic wave theory
地震波理论研究板块界面摩擦力分布及大推力地震发生
- 批准号:
23H01271 - 财政年份:2023
- 资助金额:
$ 200万 - 项目类别:
Grant-in-Aid for Scientific Research (B)
Combinatorial Set Theory, Forcing, and Large Cardinals
组合集合论、强迫和大基数
- 批准号:
2308248 - 财政年份:2023
- 资助金额:
$ 200万 - 项目类别:
Continuing Grant
CAREER: Toward Hierarchical Game Theory and Hybrid Learning Framework for Safe, Efficient Large-scale Multi-agent Systems
职业:面向安全、高效的大规模多智能体系统的分层博弈论和混合学习框架
- 批准号:
2144646 - 财政年份:2022
- 资助金额:
$ 200万 - 项目类别:
Continuing Grant
Electromagnetic Scattering from a Large Cavity in Heterogeneous Media: Theory and Algorithm
异质介质中大空腔的电磁散射:理论和算法
- 批准号:
567866-2022 - 财政年份:2022
- 资助金额:
$ 200万 - 项目类别:
Postdoctoral Fellowships
Model theory of D-large fields and connections to representation theory.
D-大域的模型理论以及与表示理论的联系。
- 批准号:
EP/V03619X/1 - 财政年份:2022
- 资助金额:
$ 200万 - 项目类别:
Research Grant