AF: Small: Unconditional Lower Bounds in Approximability and Cryptography

本项目的重点是两个相关的研究项目，一个是关于近似算法理论中的无条件下界，另一个是关于密码学基础中的无条件下界。这样的问题的一个例子是，给定一个3-可着色图，有效地找到一个3-着色，该3-着色适当地着色尽可能多的边。完善的“唯一对策”理论及其与半定规划松弛法的关系并不适用于可满足的实例。这个项目探讨了Khot的“2-to-1博弈猜想”及其在此类问题中的作用，考虑了诸如2-to-1博弈的半定规划松弛的完整性缺口实例的存在，2-to-1博弈的近似算法的存在，以及类似于Raghavendra为唯一游戏证明的“普遍性”结果的可能性。在密码学的基础中，该项目利用很少应用于密码分析的理论计算机科学方法来解决此类问题。 该项目将研究Hellman-Fiat-Naor通用单向函数反相器的推广和改进，Goldreich单向函数候选者在各种限制形式的攻击下的安全性，以及伪随机生成器和散列函数的有效构造在受限形式的攻击下的安全性。该项目的近似算法部分的进展将进一步发展一个最活跃和最成功的目前的研究计划在理论计算机科学，通过澄清一个重要的，但仍然知之甚少的理论部分。过去在这一领域的进展已经引起了理论计算机科学家和纯数学家的广泛兴趣。该项目的密码学部分的进展将在理论密码学和密码分析之间带来新的联系，通过将前者研究社区的技术应用于后者感兴趣的问题。该项目有助于长期目标，开发新的通用工具，可用于验证加密原语的安全性。

The focus of this project is on two related research programs, one concerned with unconditional lower bounds in the theory of approximation algorithms and one concerned with unconditional lower bounds in the foundations of cryptography.In the study of approximation algorithms, this project focuses on the complexity of finding approximate solutions to satisfiable constraint satisfaction problems; an example of such a problem is, given a 3-colorable graph, to efficiently find a 3-coloring that properly colors as many edges as possible. The well developed theory of "Unique Games," and its relationship with the power of Semidefinite Programming relaxations, does not apply to satisfiable instances. This project explores Khot's "2-to-1 games conjecture" and its role in such questions, considering issues such as the existence of integrality gap instances for Semidefinite Programming relaxation of 2-to-1 games, the existence of approximation algorithms for 2-to-1 games, and the possibility of a `"universality" results similar to the one proved by Raghavendra for unique games.In the foundations of cryptography, this project attacks problems in cryptoanalysis with theoretical computer science methods that have rarely been applied to such problems. The project will study generalizations and improvements of the Hellman-Fiat-Naor generic one-way function inverter, the security of Goldreich's one-way function candidate under various restricted forms of attack, and the security of efficient constructions of pseudorandom generators and hash functions under restricted forms of attack.Progress in the approximation algorithms component of the project will further develop one of the most active and successful current research programs in theoretical computer science, by clarifying an important but still poorly understood part of the theory. Past advances in this area have been of broad interest to theoretical computer scientists and pure mathematicians.Progress in the cryptography component of the project will bring a new connection between theoretical cryptography and cryptoanalysis, by applying techniques from the former research community to problems of interest to the latter. The project contributes to the long-term goal to develop new general tools that can be used to validate the security of cryptographic primitives.