Special Year in Computational Complexity Theory

计算复杂性理论特别年

基本信息

  • 批准号:
    9987077
  • 负责人:
  • 金额:
    $ 30万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2000
  • 资助国家:
    美国
  • 起止时间:
    2000-09-01 至 2001-08-31
  • 项目状态:
    已结题

项目摘要

Avi Wigderson9987077This project will support three senior researchers to participate in a special year on computational complexity theory at the Institute for Advanced Studies. These researchers will attract the participation of other top researchers in computational complexity. Computational complexity theory has opened up one of the most exciting fields of scientific and mathematical research over the last 20 years, with dramatic achievements and fundamental understandings appearing at a high rate. One obvious explanation for the recent progress in this field is that this research is guided by a few clear and focused questions, deeply motivated on scientific, practical and philosophical grounds. The most central of these are:P=NP?, or more generally, are the many natural computational problems we can't solve really difficult?NP=coNP?, or more generally, what constitutes a difficult theorem to prove:P=BPP?, or more generally, does randomization really help efficient computation?BPP=QP?, or more generally, can quantum mechanics be efficiently simulated classically?Resolving any of these questions is clearly very long term goal, but each has stimulated the development of concepts, problems, proof techniques and results which start paving a path towards a possible resolution.But what really characterized the progress, and explained much of the successes so far, was the unveiling of many rich and beautiful connections between the sets of concepts and sub-problems each of these major questions gave rise to. There is little doubt that such connections are, and will be, the foundation for understanding the major questions of complexity theory. Indeed, these connections are what is making the complex world of computational complexity into a theory. The focus of this special year at the Institute will be to better understand these connections and their implications, to unify and extend them, and to look for new ones.
该项目将支持3名高级研究人员参加高等研究院计算复杂性理论特别年。这些研究人员将吸引其他计算复杂性领域的顶尖研究人员的参与。在过去的20年里,计算复杂性理论开辟了科学和数学研究中最令人兴奋的领域之一,取得了惊人的成就,并迅速得到了基本的理解。对这一领域最近进展的一个显而易见的解释是,这项研究是由几个清晰而集中的问题指导的,这些问题深深受到科学、实践和哲学基础的推动。其中最核心的是:P=NP?或者更普遍地说,我们无法解决的许多自然计算问题真的很难吗?或者更一般地说,是什么构成了一个难以证明的定理:P=BPP?或者更普遍地说,随机化真的有助于高效计算吗?或者更一般地说,量子力学可以被有效地模拟吗?解决这些问题显然是一个非常长期的目标,但每个问题都刺激了概念、问题、证明技术和结果的发展,开始为可能的解决方案铺平道路。但是,这一进步的真正特点,以及迄今为止许多成功的原因,是揭示了这些主要问题所产生的概念集和子问题之间的许多丰富而美丽的联系。毫无疑问,这种联系现在是,将来也将是理解复杂性理论主要问题的基础。事实上,正是这些联系将计算复杂性的复杂世界变成了一个理论。在这个特殊的年份,研究所的重点将是更好地理解这些联系及其影响,统一和扩展它们,并寻找新的联系。

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ 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码张量积的鲁棒局部可测试性
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
  • 资助金额:
    $ 30万
  • 项目类别:
    Continuing Grant
AF: Large: Theory of Computation - Pushing the State-of-the-Art
AF:大:计算理论 - 推动最先进的技术
  • 批准号:
    1412958
  • 财政年份:
    2014
  • 资助金额:
    $ 30万
  • 项目类别:
    Continuing Grant
CDI Type II: Pseudorandomness
CDI II 型:伪随机性
  • 批准号:
    0835373
  • 财政年份:
    2008
  • 资助金额:
    $ 30万
  • 项目类别:
    Standard Grant
Lie Groups, Representations and Discrete Mathematics
李群、表示和离散数学
  • 批准号:
    0542278
  • 财政年份:
    2006
  • 资助金额:
    $ 30万
  • 项目类别:
    Standard Grant
ITR Medium Award: Computational Complexity Theory 2003
ITR 中奖:计算复杂性理论 2003
  • 批准号:
    0324906
  • 财政年份:
    2003
  • 资助金额:
    $ 30万
  • 项目类别:
    Continuing Grant
Basic Research in Theoretical Computer Science and Discrete Mathematics
理论计算机科学与离散数学基础研究
  • 批准号:
    9987845
  • 财政年份:
    2000
  • 资助金额:
    $ 30万
  • 项目类别:
    Standard Grant

相似海外基金

CDT year 1 so TBC in Oct 2024
CDT 第 1 年,预计 2024 年 10 月
  • 批准号:
    2879865
  • 财政年份:
    2027
  • 资助金额:
    $ 30万
  • 项目类别:
    Studentship
HSI Pilot Project: Institutionalizing a Teaching and Learning Excellence Community of Practice focused on First-Year Student Success in STEM
HSI 试点项目:将卓越教学和学习实践社区制度化,重点关注一年级学生在 STEM 方面的成功
  • 批准号:
    2345247
  • 财政年份:
    2024
  • 资助金额:
    $ 30万
  • 项目类别:
    Standard Grant
HSI Implementation and Evaluation Project: Leveraging Social Psychology Interventions to Promote First Year STEM Persistence
HSI 实施和评估项目:利用社会心理学干预措施促进第一年 STEM 的坚持
  • 批准号:
    2345273
  • 财政年份:
    2024
  • 资助金额:
    $ 30万
  • 项目类别:
    Standard Grant
Participant Support for the Kahramanmaraş, Turkey, Earthquake Sequence One-year Anniversary Programming at the 2024 EERI Annual Meeting; Seattle, Washington; 9-12 April 2024
在 2024 年 EERI 年会上为土耳其卡赫拉曼马拉地震一周年纪念活动提供支持;
  • 批准号:
    2418579
  • 财政年份:
    2024
  • 资助金额:
    $ 30万
  • 项目类别:
    Standard Grant
Expanding Pathways for Preparing the Next Generation of Engineers: First-Year Engineering 2.0 (FYE2.0)
拓展培养下一代工程师的途径:一年级工程 2.0 (FYE2.0)
  • 批准号:
    2337003
  • 财政年份:
    2024
  • 资助金额:
    $ 30万
  • 项目类别:
    Standard Grant
Extracurricular Instrument Training Experience for Students at a Two-Year College
两年制大学学生课外乐器培训体验
  • 批准号:
    2323078
  • 财政年份:
    2024
  • 资助金额:
    $ 30万
  • 项目类别:
    Standard Grant
What are the implications of health inequalities such as parental education and household income in BAME 11-16 year old's mental health in Wales
父母教育和家庭收入等健康不平等对威尔士 BAME 11-16 岁心理健康有何影响
  • 批准号:
    2875399
  • 财政年份:
    2024
  • 资助金额:
    $ 30万
  • 项目类别:
    Studentship
Conference: A Virtual Workshop for Two-Year College Geoscience Faculty to Develop National Science Foundation Grant Proposals
会议:两年制大学地球科学教师制定国家科学基金会拨款提案的虚拟研讨会
  • 批准号:
    2349758
  • 财政年份:
    2024
  • 资助金额:
    $ 30万
  • 项目类别:
    Standard Grant
Conference: Two-Year College Data Science Initiative (TYCDSI) Workshop
会议:两年大学数据科学计划 (TYCDSI) 研讨会
  • 批准号:
    2402290
  • 财政年份:
    2024
  • 资助金额:
    $ 30万
  • 项目类别:
    Standard Grant
Using Advanced Technology to Enhance Learning and Teaching in Science Labs at Two-Year Colleges
利用先进技术加强两年制学院科学实验室的学习和教学
  • 批准号:
    2329563
  • 财政年份:
    2024
  • 资助金额:
    $ 30万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了