Randomness, Non-determinism, and Symmetry Breaking
Randomness, Non-determinism, and Symmetry Breaking
批准号:
0830719
负责人:
Leonid Levin
金额:
$0.0万
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2008
资助国家:
美国
项目状态:
已结题
起止时间:
2008-08-01 至 2011-01-31
中文摘要
计算机技术的爆炸性发展超过了理论理解,使其许多支柱摇摇欲坠。举一个极端的例子,如果P=NP或单向函数不存在,那么所有公钥加密和许多对国家和个人安全至关重要的工具都将永久失效。在这种情况下(不太可能,但有可能),许多计算机基础设施将不得不以不那么令人印象深刻的规模进行重新设计。另一方面,由于对基本问题的理论认识不足,许多重大进步至今仍无法预见。计算很少在确定性隔离中运行。它们与用户和对手交互,与算法调用或上下文生成的随机事件交互,与来自系统、硬件和分布式基础设施等的延迟和故障交互。其中一些相互作用很难建模,但即使是那些有简单数学模型的相互作用也很难分析。随机性和非确定性是确定性计算概念衍生出来的两个基本“自由”,在计算理论中起着至关重要的作用。然而,我们对它们的作用和力量的了解很少。即使是在理解这些现象以及它们彼此之间和与其他概念之间的关系方面取得渐进的进展也将是重要的。在这个方向上取得成就的一个例子是发现单向函数和确定性随机生成之间的一般关系。另一个是透明(也称为全息或PCP)证明和计算的概念。在这些领域中,已经积累了许多有趣的技术,这些技术对不同的结果非常有用:低次多项式和低周期群上的傅里叶变换,与纠错码和哈希、展开图、层次结构等经典结果相关。PI将继续调查这些概念以及这些和其他相关技术的力量。对称是许多领域的中心现象之一。在计算中,它可以简化分析,提供一致性和冗余,例如,用于纠错。另一方面,它可能导致不确定、死锁和复杂的初始化和计算过程的组织。打破对称性和保持对称性同样重要。目的是研究一些对对称破缺有用的数学和算法工具。例子包括Thue序列,非周期平铺,从流形到图的平面连接概念的扩展,等等。这项工作将通过讲座、论文和网页(PI自己和其他人的网页)传播结果,促进发现和理解。这项研究对许多偏远和偏远地区都有影响。事实上,PI感兴趣的概念,例如随机性,在广泛的知识领域中是基础的。
英文摘要
Explosive development of computer technology outpaces theoretical understanding and leaves many of its pillars on shaky ground. As an extreme example, if it turns out that P=NP or that one-way functions do not exist, all of public-key cryptography and many tools crucial for national and personal security would be permanently incapacitated. In this (unlikely but possible) event, much of the computer infrastructure would have to be redesigned on a less impressive scale. On the other hand, many great advances cannot be foreseen even now due to insufficient theoretical understanding of basic issues.Computations rarely run in deterministic isolation. They interact with users and adversaries, with random events called by algorithms or generated by the context, with delays and glitches from the system, hardware, and distributed infrastructure, etc. Some of these interactions are hard to model, but even those with straightforward mathematical models are often very hard to analyze. Randomness and non-determinism are two basic "freedoms" branching out of the concept of deterministic computation which play a crucial role in computing theory. Yet our understanding of their role and power is minimal. Even a gradual progress in understanding these phenomena and their relationship to each other and to other concepts would be important.An example of achievements in this direction is the discovery of generic relationship between one-way functions and deterministic generation of randomness. Another is the concept of transparent (also called holographic, or PCP) proofs and computations. A number of interesting techniques useful for quite different results in these areas have been accumulated: low-degree polynomials and Fourier transforms over low-periodic groups, related to classical results on error-correcting codes and hashing, expander graphs, hierarchic structures, etc. The PI will continue his investigation of such concepts and of the power of these and other related techniques.Symmetry is one of the central phenomena in many fields. In computation it can simplify analysis, provide uniformity and redundancy useful, e.g., for error-correction. On the other hand, it can cause indecisiveness, deadlocks and complicate initialization and organization of computing processes. Breaking symmetries is as essential a task as maintaining them. A study of a number of mathematical and algorithmic tools useful for symmetry breaking is intended. Examples include Thue sequences, aperiodic tilings, extensions of the concept of flat connections from manifolds to graphs, and others.The work will advance discovery and understanding via dissemination of the results through talks, papers, and Web pages, PI's own and those of others. This research has implications in many close and remote areas. Indeed, the concepts the PI is interested in such as, e.g., randomness, are fundamental in a broad variety of fields of knowledge.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
AF:EAGER: Randomness, Non-determinism, and Symmetry Breaking
-
批准号:1049505
-
项目类别:Standard Grant
-
资助金额:$10.0万
-
财政年份:2010
-
负责人:Leonid Levin
-
依托单位:
Randomness and Non-Determinism
-
批准号:0311411
-
项目类别:Continuing Grant
-
资助金额:$25.0万
-
财政年份:2003
-
负责人:Leonid Levin
-
依托单位:
Randomness in Computing
-
批准号:9820934
-
项目类别:Standard Grant
-
资助金额:$32.5万
-
财政年份:1999
-
负责人:Leonid Levin
-
依托单位:
Randomness and Non-Determinism
-
批准号:9610455
-
项目类别:Standard Grant
-
资助金额:$10.0万
-
财政年份:1997
-
负责人:Leonid Levin
-
依托单位:
Randomness in Computing
-
批准号:9015276
-
项目类别:Continuing Grant
-
资助金额:$30.03万
-
财政年份:1991
-
负责人:Leonid Levin
-
依托单位:
Randomness in Computing
-
批准号:8607492
-
项目类别:Continuing Grant
-
资助金额:$30.0万
-
财政年份:1986
-
负责人:Leonid Levin
-
依托单位:
Informational Complexity and Computational Efficiency (Computer Research)
-
批准号:8304498
-
项目类别:Continuing Grant
-
资助金额:$14.72万
-
财政年份:1983
-
负责人:Leonid Levin
-
依托单位:
Algorithmic Complexity Theory and Applications
-
批准号:8104211
-
项目类别:Standard Grant
-
资助金额:$3.5万
-
财政年份:1981
-
负责人:Leonid Levin
-
依托单位:
国内基金
海外基金
登录
查看更多内容
Domain理论和non-Hausdorff拓扑学中幂构造的若干问题研究
-
批准号:12471070
-
项目类别:面上项目
-
资助金额:44.00万元
-
批准年份:2024
-
负责人:徐晓泉
-
依托单位:
新冠病毒非受体结合基序(non-RBM)抗原表位及其互作抗体的表征和机制研究
-
批准号:82471871
-
项目类别:面上项目
-
资助金额:50.00万元
-
批准年份:2024
-
负责人:迟象阳
-
依托单位:
Non-CG DNA甲基化平衡大豆产量和SMV抗性的分子机制
-
批准号:32301796
-
项目类别:青年科学基金项目
-
资助金额:30万元
-
批准年份:2023
-
负责人:寻红卫
-
依托单位:
long non-coding RNA(lncRNA)-activatedby TGF-β(lncRNA-ATB)通过成纤维细胞影响糖尿病创面愈合的机制研究
-
批准号:LQ23H150003
-
项目类别:省市级项目
-
资助金额:--
-
批准年份:2023
-
负责人:厉怡
-
依托单位:
染色体不稳定性调控肺癌non-shedding状态及其生物学意义探索研究
-
批准号:82303936
-
项目类别:青年科学基金项目
-
资助金额:30万元
-
批准年份:2023
-
负责人:张嘉涛
-
依托单位:
变分法在双临界Hénon方程和障碍系统中的应用
-
批准号:12301258
-
项目类别:青年科学基金项目
-
资助金额:30.00万元
-
批准年份:2023
-
负责人:王聪
-
依托单位:
BTK抑制剂下调IL-17分泌增强CD20mb对Non-GCB型弥漫大B细胞淋巴瘤敏感性
-
批准号:
-
项目类别:省市级项目
-
资助金额:10.0万元
-
批准年份:2022
-
负责人:李庆山
-
依托单位:
Non-TAL效应子NUDX4通过Nudix水解酶活性调控水稻白叶枯病菌致病性的分子机制
-
批准号:--
-
项目类别:青年科学基金项目
-
资助金额:30万元
-
批准年份:2022
-
负责人:郭宝佃
-
依托单位:
一种新non-Gal抗原CYP3A29的鉴定及其在猪-猕猴异种肾移植体液排斥反应中的作用
-
批准号:--
-
项目类别:地区科学基金项目
-
资助金额:33万元
-
批准年份:2022
-
负责人:王毅
-
依托单位:
非经典BAF(non-canonical BAF,ncBAF)复合物在小鼠胚胎干细胞中功能及其分子机理的研究
-
批准号:32170797
-
项目类别:面上项目
-
资助金额:58万元
-
批准年份:2021
-
负责人:张文胜
-
依托单位: