This project falls within the discipline of computational complexity, which studies the power and limitations of efficient computation. The area develops models that represent the various capabilities of digital computing devices. It aims to determine which transformations can be realized in such a way that the amount of time, memory space, and other resources scale moderately with the input size.
Of central importance is the class of so-called NP-complete problems. The latter contains thousands of computational problems from all branches of science and engineering that have been shown equivalent in the sense that an efficient algorithm for one implies such an algorithm for all. The P vs NP question asks whether efficient algorithms exist for these problems. It constitutes the main open question in theory of computing and is one of the seven millennium prize problems proposed by the Clay Mathematics Institute as grand challenges for the 21st century. A positive answer would open up tremendous possibilities that would affect most human endeavors. On the other hand, it would also yield a way to break the cryptographic systems that are currently in use and, in fact, imply the impossibility of secure communication over the internet.
This project fits into the quest to settle that fundamental and important problem. In particular, it establishes a tight connection between that question and the amount by which instances of NP-complete problems can be efficiently compressed without affecting their solvability.
If P=NP, then NP-complete decision problems can be efficiently compressed to a single bit. On the other hand, under a hypothesis that is somewhat stronger than P<>NP, the PI has established that NP-complete problems like satisfiability and vertex cover do not allow any nontrivial amount of compression. The approach hinges on the existence of high-density subsets of the integers without arithmetic progressions of length 3. This project further develops that approach and investigates its implications for other computational parameters of interest. The project also involves a systematic study of the use of high-density subsets of the integers without arithmetic progressions of certain lengths in computational complexity, and the development of new applications.
The above construction handles deterministic compression schemes. For cryptographic and other reasons the extension to the randomized setting is of interest. One possible approach involves derandomization. In this context the project investigates the potential of typically-correct derandomization, where one aims for efficient deterministic simulations that behave correctly on most but not necessarily all inputs of any given length.
The main intellectual merit of this project are limits to the compressibility of some central computationally difficult problems. Some computational problems have the property that, although their solution may be difficult to compute, it is easy to compress the problem in the following sense - a given problem statement can easily be transformed into a statement that is equivalent but much shorter. A natural limit for the compressibility of any problem is the length of the solution to the problem, and several interesting problems are known to be compressible to a size that is the square of that limit. For a large class of computational problems, this project shows that the square is the best one can achieve unless the problem is not computationally difficult to begin with. The class includes central NP-hard problems such as vertex cover and feedback vertex set. Another intellectual merit of the project deals with the power of randomness in computation, in particular for the fundamental problem of checking whether two arithmetic formulas are equivalent. A natural approach is to plug in random numbers for all the variables, and verify whether both formulas evaluate to the same number. For general arithmetic formulas, no deterministic procedure of similar efficiency is known. This project establishes an efficient deterministic procedure for formulas in which every variable can only appear a constant number of times. Broader impacts of the project include the training of five graduate students and one postdoctoral student. Two of those students have taken up positions as assistant professors by now; the other four are still working towards their doctoral degrees. Another broader impact is the development of lecture notes for a course on efficient deterministic simulations of randomized processes.
