Average-Case Complexity, Derandomization and Inapproximability

本提案描述了计算复杂性的研究和教育工作，在平均情况复杂性，非随机化和不可逼近性三个领域。非随机化是用相当有效的确定性算法模拟概率算法的任务；不可逼近性是研究组合优化问题寻找近似解的复杂性；平均原因复杂性是复杂性理论的一个领域，它研究的算法在大多数情况下都能很好地工作，但不一定是所有的输入。这三个紧密相连的领域有着丰富的技术成果和重要的开放性问题。在过去的几年里，一些新的技术和见解得到了发展，这表明长期存在的开放性问题的可追溯性以及新问题的重要性。更广泛地传播这些最新的见解、技术和猜想也很重要。知识的优点。研究将集中于每个领域的一些基本问题，以及这些领域之间的联系。在这里，我们提到PI和他的学生将要研究的一些问题。在非随机化的主题上，PI将对Reingold最近在无向连接的随机漫步算法的非随机化方面的突破进行推广。PI正在与Dinur， Reingold和Vadhan一起进行工作，将结果推广到任意随机对数空间算法。在平均情况下，PI将解决这样一个问题：密码学可以基于NPhardness吗？Ajtai, Dwork， Micciancio Regev等人在基于格的密码系统上的工作给了一个肯定答案的希望，而PI和Bogdanov最近的工作给出了一个主要的否定答案。这项建议描述了对该问题采取一般性否定解决办法的工作。在平均情况复杂度和不可逼近性之间的交叉点，PI将研究证明随机k-SAT距离的不可满足性的复杂性，以及假设该问题的难解性可以证明的不可逼近性结果。在基于概率可检验证明（pcp）的不可逼近性结果的主题上，PI将致力于构建“二对一”pcp，这是对Khot猜想的“唯一对策”的弱化，然后使用这些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.