Average-Case Complexity, Derandomization and Inapproximability

平均情况复杂性、去随机化和不可近似性

• 批准号: 0515231
• 负责人: Luca Trevisan
• 金额: $ 20万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-06-15 至 2008-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0515231&HistoricalAwards=false
• 关键词: Average; Case; Complexity; Derandomization; Inapproximability

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.

该提案描述了计算复杂性方面的研究和教育工作，包括平均情况复杂性，去随机化和不可逼近性三个领域。去随机化（Derandomization）是一项用确定性算法模拟概率算法的任务;不可近似性（Inapproximability）是研究寻找组合优化问题近似解的复杂性;平均复杂性（averagecasecomplicity）是复杂性理论的一个领域，研究在大多数（但不一定是所有）输入下都能很好地工作的算法。 这三个紧密相连的领域有着丰富的技术深度成果和重要的开放问题。在过去的几年里，已经开发了一些新的技术和见解，这表明了长期存在的开放问题的可处理性以及新问题的重要性。更广泛地传播这些最新的见解、技术和知识也很重要。研究将侧重于每个领域的一些基本问题，以及这些领域之间的联系。在这里，我们提到了PI和他的学生将要研究的一些问题。 关于去随机化的主题，PI将致力于Reingold最近对无向连接的随机行走算法的突破性去随机化的推广。PI正在与Dinur，Reingold和Vadhan进行合作，将结果推广到任意随机对数空间算法。 在平均情况下的复杂性，PI将工作的问题：密码学可以基于NPhardness？Ajtai、Dwork、Micciancio Regev和其他人对基于格的密码系统的研究给出了一个肯定的答案，而PI和Bogdanov最近的研究给出了一个部分否定的答案。这项建议阐述了为全面消极解决这一问题而开展的工作。 在平均情况复杂性和不可近似性之间的交叉点上，PI将研究证明随机k-SAT问题的不可满足性的复杂性，以及假设该问题的难处理性可以证明的不可近似性结果。关于基于概率可检验证明（PCP）的不可近似性结果，PI将致力于构建“二对一”PCP，这是Khot提出的“独特博弈”的弱化，然后使用此类PCP来证明不可近似性结果，而无需诉诸未经证明的独特博弈猜想。该提案支持两名研究生，他们将与PI一起研究这里描述的问题，并在国际会议上展示他们的结果。 伯克利的三门研究生课程将受到这笔赠款的影响。明年将编写一份关于平均情况复杂性的广泛调查报告，并计划在下一年编写另一份调查报告。 这个建议中提出的几个问题是基本的，为解决这些问题而设计的方法可能会导致在不相关领域的其他发现。将密码学建立在尽可能弱的假设基础上的问题在计算机科学和其他领域引起了广泛的兴趣。