AF: Small: Information Theory-Based Methods for Hardness Amplification and Compression

本项目旨在研究理论计算机科学和信息论中的两类问题。第一个是关于硬度放大。这里的目标是找到方法来处理在某些计算模型中难以计算的函数，以获得明显更难计算的新函数。例如，在通信复杂性方面，人们可能认为计算一个功能的k个副本应该花费k倍的通信时间，但到目前为止，我们不知道如何证明这一点。以前的工作表明，通信必须以大约k的平方根的倍数增长，但这是否能增加到k的倍数还有待观察。这种问题的另一个有意义的领域是流传输算法。在流算法中，输入以无法存储的海量数据流的形式到达。目标是使用尽可能少的内存来计算数据的函数。人们可能会认为并行处理k个独立的数据流应该需要k倍的内存，但我们不知道如何证明这一点。类似的问题也可以被问到，关于放大近似算法的难度，并表明用自己组成一个函数会增加它的电路深度。这类问题与证明下界有关，这是理论计算机科学的中心目标。第二类问题是关于压缩。今天，我们已经很好地理解了如何压缩单个消息，以便表示它们所需的比特数或多或少等于它们所携带的信息。在这里，可以使用香农的熵函数来测量信息，或者在随机传输的情况下，使用输入和消息之间的互信息来测量信息。但是，如果我们在几个当事人之间有一个互动的沟通过程，如何减少互动中的沟通，使沟通接近各方之间传达的信息量，这是不清楚的。这个问题与上面讨论的放大函数的通信复杂性的问题密切相关。以前的工作已经展示了如何减少传递小信息的协议的通信，并且这种压缩方案被证明是有用的，以证明计算一个函数的多个副本必须需要更大的通信。事实上，最佳的压缩方案将在设定硬度放大时给出最佳结果。找到这样一个方案是这个项目的一个主要目标。该项目还旨在研究流算法所使用的内存压缩。在给定流算法的情况下，我们是否可以一直减少算法的内存使用量，直到使用的位数接近算法存储的信息量。在这种情况下，不清楚正确的信息度量应该是什么，定义有意义的信息度量是另一个目标。将该提案的问题联系在一起的共同主题是适用于这些问题的基于信息论的方法。

This project aims to investigate two kinds of problems in theoretical computer science and information theory. The first is about Hardness Amplification. Here the goal is to find ways to manipulate functions that are hard to compute in some computational model to obtain new functions that are significantly harder to compute. For example, in communication complexity, one might expect that computing k copies of a functionality should take k times the communication, but to date we do not know how to prove this. Prior work has shown that the communication must grow by a factor of roughly the square root of k, but it remains to be seen whether this can be increased to a factor of k. Another domain where this kind of problem makes sense is for streaming algorithms. In a streaming algorithm, the input arrives as a massive data stream that cannot be stored. The goal is to compute a function of the data using as little memory as possible. One might expect that handling k independent streams of data in parallel should require k times the memory, yet we do not know how to prove this. Similar questions can be asked about amplifying the hardness of approximation algorithms, and showing that composing a function with itself increases its circuit depth. This kind of question is related to proving lowerbounds, a central goal of theoretical computer science.The second kind of problem is about compression. Today we have a good understanding of how single messages can be compressed so that the number of bits it takes to represent them is more or less equal to the information that they carry. Here the information can be measured using Shannon's Entropy function, or in the case of randomized transmissions, the mutual information between the inputs and the messages. However, if we have an interactive communication process between several parties, it is not clear how to reduce the communication in the interaction so that the communication is close to the amount of information conveyed between the parties. This problem is closely related to the problem of amplifying the communication complexity of a function, discussed above. Prior work has shown how to reduce the communication of a protocol that conveys small information, and such a compression scheme turns out to be useful to prove that computing many copies of a function must require larger communication. Indeed, an optimal compression scheme would give an optimal result in the setting of hardness amplification. Finding such a scheme is a major goal of this project. This project also aims to study the compression of memory used by streaming algorithms. Given a streaming algorithm, can we always reduce the memory usage of the algorithm until the number of bits used is close to the amount of information stored by the algorithm. In this setting, it is not clear what the right measure of information should be, and defining a meaningful measure of the information is another goal.The common theme tying the problems of this proposal together is an information theory based method that is applicable to these problems.