Computational Complexity and Information Theory

提案号：9912342PI: Madhu SudanInstitution: mit1计算机科学理论的广泛目标之一是确定似乎难以计算的函数，如果可能的话，证明它们确实很难。进一步的目标是量化一个函数的计算难度，对于一些适当的硬度度量，并找到在这个度量下非常困难的函数。例如，在最常见的计算难度应用（即密码学）中，需要知道给定的硬函数（如离散对数或RSA解密）对几乎所有输入都是困难的（而不是对某些对抗性选择的输入）。为了形式化这样的陈述，人们需要找到硬度的良好度量，并开发分析它们的工具。近年来，许多研究文章提出了硬度的不同概念，并对其进行了分析。这些结果中的许多可以被认为是基于计算复杂性的信息的抽象定量概念。结果表明，给定一个较难的函数，就可以构造一个更难的函数，从某种意义上说，即使计算有关较难函数的少量信息，也可以有效地完美计算给定函数。此外，这些结果都有一个共同的主题，即依赖于最先进的结果，即纠错码的有效列表可解码性。本研究计划将系统研究解码算法对复杂性理论的影响。它将检查一系列的主题，其中连接可能被证明是富有成效的。该研究项目还将研究在复杂性理论中寻找新工具所影响的编码理论中的新问题。该项目最雄心勃勃的部分是探索NP问题的平均情况硬度的编码理论方法。在NP中寻找平均情况下的难题是复杂性理论的基本任务之一。平均难度问题的存在是密码学的必要条件。它还解释了一些优化问题的最坏情况硬度和经验观察到的容易程度之间的表面对比。因此，这一方向的进展将对计算机科学产生重大影响。

Proposal Number: 9912342PI: Madhu SudanInstitution: MITOne of the broad goals of the theory of computer science is to identify functions that seem hard to compute, and if possible to prove that they are indeed hard. A further goal is to quantify how hard a function is to compute, for some appropriate measure of hardness, and to find functions that are very hard under this measure. For example, in the most common application of computational hardness, namely cryptography, one needs to know that a given hard function, such as the discrete logarithm or RSA decryption, is hard on almost all inputs (rather than on some adversarially chosen inputs). In order to formalize such statements, one needs to find good measures of hardness and develop tools to analyze them.In the recent pasta number of research articles have proposed different notions of hardness and analyzed them. Many of these results can be thought of as abstracting quantitative notions of information based on computational complexity. The results show that given a hard function, one can construct a much harder one, in the sense that computing even a small amount of information about the harder function allows for efficient perfect computation of the given function. Further these results share a common theme of relying on state-of-the-art results on the efficient listdecodability of error-correcting codes.This research project will perform a systematic study of the influence of decoding algorithms on complexity theory. It will examine a series of topics where a connection may prove to be fruitful. The research project will also examine new questions in coding theory influenced by the search for new tools in complexity theory. The most ambitious element of the project is the exploration of a coding theoretic approach to average case hardness of problems in NP. The search for average-case hard problems within NP is one of the fundamental quests of complexity theory. Existence of problems that are hard on the average is a necessary condition for cryptography. It also explains seeming contrast between worst-case hardness and empirically observed easiness of some optimization problems. Thus progress in this direction would be of great impact to computer science.