课题基金 / 基金详情

Average-Case Complexity, Derandomization and Inapproximability

Average-Case Complexity, Derandomization and Inapproximability
平均情况复杂性、去随机化和不可近似性
批准号:
0515231
负责人:
Luca Trevisan
金额:
$20.0万
依托单位国家:
美国
项目类别:
Continuing Grant
财政年份:
2005
资助国家:
美国
项目状态:
已结题
起止时间:
2005-06-15 至 2008-05-31

项目摘要

项目成果

Luca Trevisan的其他基金

相似基金

相关文献

中文摘要
翻译
这项建议描述了在平均情况复杂性、去随机化和不可逼近三个领域的计算复杂性方面的研究和教育工作。去随机化是用相对有效的确定性算法来模拟概率算法的任务;不可逼近性是研究找到组合优化问题的近似解的复杂性;平均复杂性是复杂性理论的领域,它研究在大多数(但不一定是所有)输入上工作良好的算法。这三个紧密相连的领域有着丰富的技术深度成果和重要的开放问题。在过去的几年里,一些新的技术和见解被开发出来,这表明了长期存在的开放问题的易处理性以及新问题的重要性。更广泛地传播这些最新的见解、技术和猜想也很重要。研究将集中于每个领域中的一些基本问题,以及这些领域之间的联系。在这里,我们提到几个PI和他的学生将致力于解决的问题。在去随机化这一主题上,PI将致力于对Reingold最近突破性的无向连通性随机行走算法的去随机化进行推广。PI正在与Dinur、Reingold和Vadhan一起进行工作,以将结果推广到任意随机的日志空间算法。就平均情况的复杂性而言,PI将解决这样一个问题:密码学可以基于NPhard吗?Ajtai,Dwork,Micciancio Regev等人在基于格的密码系统方面的工作给出了肯定答案的希望,而PI和Bogdanov最近的工作给出了有限的否定答案。这项提案描述了为全面消极解决该问题所做的工作。在平均情况复杂性和不可逼近性之间,PI将研究证明随机k-SAT条件的不可满足性的复杂性,以及假设该问题的难解性可以证明的不可逼近结果。在基于概率可查证明(PCP)的不可逼近结果问题上,PI将致力于构造“2对1”的PCP,这是对霍特猜想的“唯一对策”的弱化,然后利用这些PCP来证明不可逼近结果,而不求助于未经证明的唯一对策猜想。这项提案支持两名研究生,他们将在这里描述的问题上与PI合作,并在国际会议上展示他们的结果。伯克利分校的三门研究生课程将受到这笔拨款的影响。明年将撰写一份关于平均案例复杂性的广泛调查报告,并计划在次年撰写另一份调查报告。这项提案中涉及的几个问题是根本性的,为解决这些问题而设计的方法可能会导致在无关领域的其他发现。将密码学建立在最弱的可能假设的基础上的问题在计算机科学和其他领域引起了广泛的兴趣。
英文摘要
This proposal describes research and educational work in computational complexity, in the three areas of average-case complexity, derandomization and inapproximability. Derandomization is the task of simulating probabilistic algorithms with comparably efficient deterministic ones; Inapproximability is the study of the complexity of finding approximate solutions to combinatorial optimization problems; and averagecasecomplexity is the area of complexity theory that studies algorithms that work well on most, but not necessarily all, inputs. These three strongly connected areas are rich in technically deep results and in important open questions. Several new techniques and insights have been developed in the last few years, suggesting the tractability of long-standing open questions as well as the importance of new questions. A wider dissemination of these recent insights, techniques and conjectures is also important.Intellectual Merits. The research will focus on a number of fundamental questions in each area, as well as on connections between the areas. Here we mention a few of the problems that the PI and his students will work on. On the topic the derandomization, the PI will work on a generalization of Reingold's recent breakthrough derandomization of the random walk algorithm for undirected connectivity. The PI is engaged in ongoing work with Dinur, Reingold and Vadhan to generalize the result to arbitrary randomized log-space algorithms. On average-case complexity, the PI will work on the question: can cryptography be based on NPhardness? Work by Ajtai, Dwork, Micciancio Regev and others on lattice-based cryptosystems gives hope for a positive answer, while recent work by the PI and Bogdanov gives a parital negative answer. This proposal describes work towards a general negative resolution of the question. At the intersetion between average-case complexity and inapproximability, the PI will study the complexity of certifying unsatisfiability of random k-SAT istances and the inapproximability results that can be proved assuming the intractability of this problem. On the topic of inapproximability results based on probabilistically checkable proofs (PCPs), the PI will work towards constructing "two-to-one" PCPs, a weakening of the "Unique Games" conjectured by Khot, and then use such PCPs to prove inapproximability results without resorting to the unproved Unique Games Conjecture.Broader Impact. This proposal supports two graduate students, who will work with the PI on the problems described here, and present their results at international conferences. Three graduate courses at Berkeley will be influenced by this grant. An extensive survey paper on average-case complexity will be written next year, and another survey paper is planned for the following year. Several of the questions addressed in this proposal are fundamental, and methods devised for their resolution are likely to lead to other discoveries in unrelated fields. The question of basing cryptography on the weakest possible assumptions is of broad interest in computer science and beyond.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
AF: Small: Spectral and SDP Techniques: Average-Case Analysis and Subexponential Algorithms
  • 批准号:
    1815434
  • 项目类别:
    Standard Grant
  • 资助金额:
    $50.0万
  • 财政年份:
    2018
  • 负责人:
    Luca Trevisan
  • 依托单位:
EAGER: New Graph and CSP Algorithms Based on Spectral and SDP Techniques
  • 批准号:
    1655215
  • 项目类别:
    Standard Grant
  • 资助金额:
    $10.0万
  • 财政年份:
    2016
  • 负责人:
    Luca Trevisan
  • 依托单位:
AF: Small: Graph Partitioning and Spectral Methods
  • 批准号:
    1540685
  • 项目类别:
    Standard Grant
  • 资助金额:
    $28.97万
  • 财政年份:
    2014
  • 负责人:
    Luca Trevisan
  • 依托单位:
AF: Small: Graph Partitioning and Spectral Methods
  • 批准号:
    1216642
  • 项目类别:
    Standard Grant
  • 资助金额:
    $40.0万
  • 财政年份:
    2012
  • 负责人:
    Luca Trevisan
  • 依托单位:
国内基金
海外基金
Intelligent Patent Analysis for Optimized Technology Stack Selection:Blockchain BusinessRegistry Case Demonstration
  • 批准号:
    --
  • 项目类别:
    外国学者研究基金项目
  • 资助金额:
    --
  • 批准年份:
    2024
  • 负责人:
    USHARANI HAREESH GOVINDARA JAN
  • 依托单位:
Case-Cohort数据的半参数逆回归估计和纵向数据分析
  • 批准号:
    11071137
  • 项目类别:
    面上项目
  • 资助金额:
    22.0万元
  • 批准年份:
    2010
  • 负责人:
    杨瑛
  • 依托单位: