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.
This project was in the area of computational complexity, which studies intrinsic limitations to the power of efficient algorithms. The main focus was on developing new techniques with eventual applications to cryptography and to combinatorial optimization: specifically we looked at constructions of pseudorandom generators and of "integrality gap" instances. While such objects are known to exist under certain conjectures, this project looked for unconditional constructions, which would require the use of no unproved conjecture. The main outcome of this project in the academic year 2012-2013 was a new approach to the construction of unconditional pseudorandom generator based on "iterative restriction". A paper introducing this technique appeared in the FOCS 2012 conference, due to Parikshit Gopalan, Raghu Meka, Omer Reingold, Salil P. Vadhan, and the PI, and a paper devising further applications of this technique appeared in the CCC 2013 conference, due to the PI and the PhD student TongKe Xue, who was supported by this grant. The former paper shows how to apply the iterative restriction technique to various settings, and, in particular, gives a near-optimal construction of pseudorandom generators for statistical tests computable by "read-once CNFs." The major open problems in the area of unconditional pseudo randomness are to develop optimal constructions of pseudorandom generators for depth-2 circuits and for constant-width branching programs (knowing the definitions of these technical term is not neccessary to follow this informal discussion); for both problems, which remain open, a main bottleneck was recognized to be our inability to design good pseudorandom generators for statistical tests computed by read-once CNFs, which are both a restricted type of depth-2 circuit and a restricted type of constant-width branching program. Thus, the result of the PI and his collaborator is a step toward the solution of these core questions, that have been open for more than 20 years. The latter paper makes the first progress in 20 years in the construction of pseudorandom generators which work for all statistical tests in a class called AC0, improving a result of Nisan from 1991. While working on this project, TongKe developed new expertise and greatly matured as a student. This was his first research paper. TongKe delivered the presentation at the CCC 2013 conference.
