Can one efficiently compress search problems with small witnesses into problems whose size depends on the length of the instances? Recent results have given strong negative evidence, for example, that one cannot efficiently map the problem of finding a clique of size k to a problem of size polynomial in k. These question has surprising applications to parameterized complexity, cryptography, probabilistic proof systems and structural complexity.
This project will look to extend these results to a number of different directions including showing similar results for probabilistic compression which seem to require new breakthroughs in pseudorandom generators. Also can ever compress a function f that depends on m instances of an NP problem of size n to a single instance of size polynomial in n where the AND function seems to be the major barrier. Finally this project will explore new applications of this line of research as well as other related topics in computational complexity.
While this proposal takes a theoretical approach to instance compression, in the long-term continued research in complexity will help focus efforts when trying to tackle difficult computational problems that arise in practice. This project explore these problems with graduate students as part of their thesis research. Research from this project will be desseminated through conference and invited presentations and publications in conferences, journals and on the Internet.
