Collaborative Research: Understanding, Coping with, and Benefiting From, Intractability
Collaborative Research: Understanding, Coping with, and Benefiting From, Intractability
批准号:
0832795
负责人:
Subhash Khot
金额:
$112.5万
依托单位:
依托单位国家:
美国
项目类别:
Continuing Grant
财政年份:
2008
资助国家:
美国
项目状态:
已结题
起止时间:
2008-08-15 至 2015-07-31
中文摘要
计算的困难性限制了理解自然和设计系统的能力。 对于邮递员、旅行推销员、地图管理员和数百万希望尽可能高效地完成任务的其他人来说,难以处理是一个绊脚石,但它是21世纪世纪密码学的基础,而密码学又是电子商务的支柱。 为了理解、管理和利用棘手性,必须在以多种形式和计算模型证明棘手性方面取得进展,并解开棘手性的不同形式和用途之间的相互联系。 这次探险将探索一系列不同但相互关联的计算难题,包括算法,复杂性,密码学,分析,几何,组合学和量子力学。 第一个“顽固中心”将设在普林斯顿。 为了解决阻碍计算机科学重大进步的一些最深刻和最困难的理论问题,这次远征涉及通过地理上当地参与机构之间的合作进行高度的合议互动。 外联活动包括一个积极的“妇女参与理论”方案以及针对本科生和高中生的方案。
英文摘要
Computational intractability imposes a limit on the ability to understand nature and design systems. Intractability is a stumbling block for postmen, travelling salesmen, map colorers, and millions of others who would like to complete their tasks as efficiently as possible, yet it is the foundation of 21st century cryptography, which in turn is a pillar of electronic commerce. In order to understand, manage, and exploit intractability it is imperative that progress be made on proving intractability in many forms and computational models, and on unraveling the interconnections among different forms and uses of intractability. This Expedition will explore an array of diverse but interrelated topics in computational intractability including algorithms, complexity, cryptography, analysis, geometry, combinatorics, and quantum mechanics. A "Center for Intractability," the first of its kind, will be based at Princeton. Addressing some of the deepest and hardest theoretical problems standing in the way of significant advancements in computer science, this Expedition involves a high degree of collegial interactivity through collaborations among geographically local participating institutions. Outreach includes an active "Women in Theory" program as well as programs targeting undergraduate and high-school students.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
AF: Small: Hardness of Approximation: Classical and New
-
批准号:2130816
-
项目类别:Standard Grant
-
资助金额:$35.0万
-
财政年份:2021
-
负责人:Subhash Khot
-
依托单位:
AF: Small: Analysis, Geometry, and Hardness of Approximation
-
批准号:1813438
-
项目类别:Standard Grant
-
资助金额:$50.0万
-
财政年份:2018
-
负责人:Subhash Khot
-
依托单位:
AF: Small: Challenges in Hardness of Approximation
-
批准号:1422159
-
项目类别:Standard Grant
-
资助金额:$49.59万
-
财政年份:2014
-
负责人:Subhash Khot
-
依托单位:
2010 Waterman Award
-
批准号:1061938
-
项目类别:Standard Grant
-
资助金额:$50.0万
-
财政年份:2010
-
负责人:Subhash Khot
-
依托单位:
CAREER: New Directions in Inapproximability and Probabilistically Checkable Proofs
-
批准号:0833228
-
项目类别:Continuing Grant
-
资助金额:$23.99万
-
财政年份:2008
-
负责人:Subhash Khot
-
依托单位:
CAREER: New Directions in Inapproximability and Probabilistically Checkable Proofs
-
批准号:0643626
-
项目类别:Continuing Grant
-
资助金额:$0.0万
-
财政年份:2007
-
负责人:Subhash Khot
-
依托单位:
国内基金
海外基金
登录
查看更多内容
Research on Quantum Field Theory without a Lagrangian Description
-
批准号:24ZR1403900
-
项目类别:省市级项目
-
资助金额:--
-
批准年份:2024
-
负责人:SATOSHI NAWATA
-
依托单位:
Cell Research
-
批准号:31224802
-
项目类别:专项基金项目
-
资助金额:24.0万元
-
批准年份:2012
-
负责人:程磊
-
依托单位:
Cell Research
-
批准号:31024804
-
项目类别:专项基金项目
-
资助金额:24.0万元
-
批准年份:2010
-
负责人:程磊
-
依托单位:
Cell Research (细胞研究)
-
批准号:30824808
-
项目类别:专项基金项目
-
资助金额:24.0万元
-
批准年份:2008
-
负责人:张爱兰
-
依托单位:
Research on the Rapid Growth Mechanism of KDP Crystal
-
批准号:10774081
-
项目类别:面上项目
-
资助金额:45.0万元
-
批准年份:2007
-
负责人:滕冰
-
依托单位: