CAREER: Randomized Computations and Probabilistically Checkable Proofs

职业:随机计算和概率可检查证明

基本信息

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

项目摘要

Summary:The use of randomness affects computations in dramatic and not yet fully understood ways: in algorithm design it yields simpler and more efficient ways to solve computational problems; in complexity theory it suggests new concepts and models that lead sometimes to unexpected (and far-reaching) results. This career development project involves a collection of research and educational activities related to computational randomness.The research component of this project deals with two main themes. One goal is the development of general tools that can be used to make randomized algorithms more robust, so that they can work even if they are implemented using biased, and limited, sources of randomness. Such tools are randomness extractors, procedures that convert biased distributions into almost uniform ones, and pseudorandom generators, procedures that stretch a short random input into a much longer output that has the property of being indistinguishable (a term that is given a precise technical meaning) from the uniformdistribution. The other theme of the research component is the study of probabilistically checkable proofs (PCP), a model of computation that gives a surprising characterization of NP in terms of efficient randomized proof-checking. The PCP model is the best known tool to prove results about the complexity of finding approximate solutions for NP-hard combinatorial optimization problems. The goal of this project is to look for stronger characterizations of NP in the PCP model, for more applications to the study of the approximability of optimization problems and, with special emphasis, for a simplified proof of the PCP characterization of NP, a result that currently has an exceedingly complicated proof.The educational component of this project will integrate material on randomized algorithms, pseudorandomness, and probabilistic proof-systems into existing courses on algorithms and complexity and into a new course on cryptography that the principal investigator is developing. A main goal of the educational component is to give elementary presentations of some results that have so far been confined to research-oriented graduate courses. This is unfortunate because they are relevant and entertaining, not particularly hard to explain, and can have a strong motivational influence. An extensive set of lecture notes will be developed on this material.
摘要:随机性的使用以戏剧性但尚未完全理解的方式影响计算:在算法设计中,它产生了解决计算问题的更简单、更有效的方法;在复杂性理论中,它提出了新的概念和模型,有时会导致意想不到的(和深远的)结果。这个职业发展项目涉及一系列与计算随机性相关的研究和教育活动。这个项目的研究部分涉及两个主要主题。一个目标是开发可用于使随机化算法更健壮的通用工具,以便即使使用有偏见和有限的随机性来源实施它们也可以工作。这些工具是随机性抽取器,将有偏分布转换为几乎一致分布的过程,以及伪随机生成器,伪随机生成器将较短的随机输入拉伸为具有与均匀分布无法区分(赋予精确技术含义的术语)的长得多的输出。研究部分的另一个主题是概率可核对证明(PCP)的研究,这是一种计算模型,在有效的随机证明检查方面给出了NP令人惊讶的特征。PCP模型是证明NP-Hard组合优化问题近似解的复杂性的最著名的工具。这个项目的目标是在PCP模型中寻找NP的更强的特征,以便更多地应用于优化问题的可逼近性的研究,特别是为了NP的PCP特征的简化证明,这一结果目前有一个非常复杂的证明。本项目的教育部分将把关于随机化算法、伪随机性和概率证明系统的材料整合到现有的关于算法和复杂性的课程中,并整合到首席研究者正在开发的一门新的密码学课程中。教育部分的一个主要目标是对迄今仅限于研究型研究生课程的一些成果进行初级介绍。这是不幸的,因为它们具有相关性和娱乐性,并不是特别难解释,而且可以产生强烈的动机影响。将根据这份材料编写一套广泛的课堂讲稿。

项目成果

期刊论文数量(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 }}

Luca Trevisan其他文献

Lecture Notes on Computational Complexity
  • DOI:
  • 发表时间:
    2004
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Luca Trevisan
  • 通讯作者:
    Luca Trevisan
Improved Pseudorandom Generators for Depth 2 Circuits
改进的深度 2 电路伪随机发生器
The Minority Dynamics and the Power of Synchronicity
少数派动态和同步性的力量
  • DOI:
    10.48550/arxiv.2310.13558
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
    0
  • 作者:
    L. Becchetti;A. Clementi;F. Pasquale;Luca Trevisan;Robin Vacus;Isabella Ziccardi
  • 通讯作者:
    Isabella Ziccardi
A tight characterization of NP with 3 query PCPs
具有 3 个查询 PCP 的 NP 的严格表征
A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover
顶点覆盖Lovasz-Schrijver SDP松弛的线性圆下界

Luca Trevisan的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Luca Trevisan', 18)}}的其他基金

AF: Small: Spectral and SDP Techniques: Average-Case Analysis and Subexponential Algorithms
AF:小:谱和 SDP 技术:平均情况分析和次指数算法
  • 批准号:
    1815434
  • 财政年份:
    2018
  • 资助金额:
    $ 8.39万
  • 项目类别:
    Standard Grant
EAGER: New Graph and CSP Algorithms Based on Spectral and SDP Techniques
EAGER:基于谱和 SDP 技术的新图和 CSP 算法
  • 批准号:
    1655215
  • 财政年份:
    2016
  • 资助金额:
    $ 8.39万
  • 项目类别:
    Standard Grant
AF: Small: Graph Partitioning and Spectral Methods
AF:小:图划分和谱方法
  • 批准号:
    1540685
  • 财政年份:
    2014
  • 资助金额:
    $ 8.39万
  • 项目类别:
    Standard Grant
AF: Small: Graph Partitioning and Spectral Methods
AF:小:图划分和谱方法
  • 批准号:
    1216642
  • 财政年份:
    2012
  • 资助金额:
    $ 8.39万
  • 项目类别:
    Standard Grant
AF: Small: Unconditional Lower Bounds in Approximability and Cryptography
AF:小:近似性和密码学的无条件下界
  • 批准号:
    1161812
  • 财政年份:
    2011
  • 资助金额:
    $ 8.39万
  • 项目类别:
    Continuing Grant
AF: Small: Unconditional Lower Bounds in Approximability and Cryptography
AF:小:近似性和密码学的无条件下界
  • 批准号:
    1017403
  • 财政年份:
    2010
  • 资助金额:
    $ 8.39万
  • 项目类别:
    Continuing Grant
Applications of Artihmetic Combinatorics in Computer Science
算术组合在计算机科学中的应用
  • 批准号:
    0729137
  • 财政年份:
    2007
  • 资助金额:
    $ 8.39万
  • 项目类别:
    Standard Grant
Average-Case Complexity, Derandomization and Inapproximability
平均情况复杂性、去随机化和不可近似性
  • 批准号:
    0515231
  • 财政年份:
    2005
  • 资助金额:
    $ 8.39万
  • 项目类别:
    Continuing Grant
CAREER: Randomized Computations and Probabilistically Checkable Proofs
职业:随机计算和概率可检查证明
  • 批准号:
    9984703
  • 财政年份:
    2000
  • 资助金额:
    $ 8.39万
  • 项目类别:
    Standard Grant

相似海外基金

Integration of Randomized Methods and Fast and Reliable Matrix Computations
随机方法与快速可靠的矩阵计算的集成
  • 批准号:
    2111007
  • 财政年份:
    2021
  • 资助金额:
    $ 8.39万
  • 项目类别:
    Standard Grant
Randomized Algorithms for Matrix Computations
矩阵计算的随机算法
  • 批准号:
    1929568
  • 财政年份:
    2018
  • 资助金额:
    $ 8.39万
  • 项目类别:
    Standard Grant
Randomized Algorithms for Matrix Computations
矩阵计算的随机算法
  • 批准号:
    1620472
  • 财政年份:
    2016
  • 资助金额:
    $ 8.39万
  • 项目类别:
    Standard Grant
Randomized matrix computations over finite fields
有限域上的随机矩阵计算
  • 批准号:
    89756-2008
  • 财政年份:
    2013
  • 资助金额:
    $ 8.39万
  • 项目类别:
    Discovery Grants Program - Individual
Randomized matrix computations over finite fields
有限域上的随机矩阵计算
  • 批准号:
    89756-2008
  • 财政年份:
    2011
  • 资助金额:
    $ 8.39万
  • 项目类别:
    Discovery Grants Program - Individual
Randomized matrix computations over finite fields
有限域上的随机矩阵计算
  • 批准号:
    89756-2008
  • 财政年份:
    2010
  • 资助金额:
    $ 8.39万
  • 项目类别:
    Discovery Grants Program - Individual
Randomized matrix computations over finite fields
有限域上的随机矩阵计算
  • 批准号:
    89756-2008
  • 财政年份:
    2009
  • 资助金额:
    $ 8.39万
  • 项目类别:
    Discovery Grants Program - Individual
Randomized matrix computations over finite fields
有限域上的随机矩阵计算
  • 批准号:
    89756-2008
  • 财政年份:
    2008
  • 资助金额:
    $ 8.39万
  • 项目类别:
    Discovery Grants Program - Individual
Dynamic and Randomized Load Distribution for Tree-Structured Parallel Computations on Static Interconnection Networks
静态互连网络上树结构并行计算的动态和随机负载分配
  • 批准号:
    0091719
  • 财政年份:
    2001
  • 资助金额:
    $ 8.39万
  • 项目类别:
    Continuing Grant
CAREER: Randomized Computations and Probabilistically Checkable Proofs
职业:随机计算和概率可检查证明
  • 批准号:
    9984703
  • 财政年份:
    2000
  • 资助金额:
    $ 8.39万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了