Instance Compression

人们能否有效地将带有小证人的搜索问题压缩为其大小取决于实例长度的问题？最近的结果给出了强有力的负面证据，例如，人们不能有效地将寻找大小为k的团的问题映射到大小为k的多项式的问题。这些问题在参数复杂性、密码学、概率证明系统和结构复杂性中有着令人惊讶的应用。本项目将寻求将这些结果扩展到许多不同的方向，包括显示类似的概率压缩结果，这似乎需要在伪随机生成器上取得新的突破。也可以将依赖于大小为n的NP问题的m个实例的函数f压缩为n中大小多项式的单个实例，其中AND函数似乎是主要障碍。最后，这个项目将探索这一研究路线以及其他相关主题在计算复杂性方面的新应用。虽然这项建议采取了一种理论方法来压缩实例，但从长远来看，对复杂性的持续研究将有助于集中精力解决实践中出现的计算难题。本课题将研究生作为论文研究的一部分，对这些问题进行探讨。该项目的研究将通过会议和特邀演讲以及在会议、期刊和互联网上的出版物来完成。

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.