Instance Compression

是否可以有效地将具有小证人的搜索问题压缩为大小取决于实例长度的问题？最近的结果给出了强有力的否定证据，例如，人们不能有效地将寻找大小为k的团的问题映射到大小为k的多项式的问题。这些问题在参数化复杂性，密码学，概率证明系统和结构复杂性方面具有惊人的应用。这个项目将把这些结果扩展到许多不同的方向，包括展示概率压缩的类似结果，这似乎需要在伪随机生成器方面取得新的突破。也可以将一个函数f压缩它依赖于一个大小为n的NP问题的m个实例到一个大小为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.