AF: Small: Unconditional Lower Bounds in Approximability and Cryptography

Stanford University, Stanford CA

Investigators

Abstract

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.