AF: Small: Unconditional Lower Bounds in Approximability and Cryptography

在近似算法的研究中，本课题研究了可满足约束满足问题的近似解的复杂性；一个例子是，给定一个3-可着色图，有效地找到一个适合于给尽可能多的边着色的3-着色。发展良好的“独特博弈”理论及其与半定规划松弛的关系，并不适用于可满足的实例。本项目探讨了科特的“2对1博弈猜想”及其在这类问题中的作用，考虑了2对1博弈的半定规划松弛的完整性间隙实例的存在性，2对1博弈的近似算法的存在性，以及类似于Raghavenra对独特博弈所证明的“普适性”结果的可能性。该项目将研究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.