流式计算模型中新的下界分析方法的探索

Since the notion of streaming computation is first proposed in the 1990s, lower bounds in streaming model have been a major direction of theoretical computer science and in particular the branch of complexity theory. Streaming computation became more popular in the past few years because of the explosion of data. When combined with practical application, new directions of streaming computation arise, e.g. multiple read/write (RW) stream model and online model. However, the traditional lower bound techniques (such as communication complexity) could hardly handle those new models and demands..This project aims at an accurate and elegant lower bound proof technique for streaming computation, which would help in developing better streaming algorithms. We plan to investigate the new method from three distinct directions: i) generalize the lower bound technique for the multiple read/write stream model; ii) bring ideas from leakage-resilient cryptography to show lower bounds in streaming computation; iii) compare and analyze communication complexity and streaming complexity, and then improve the traditional lower bound technique..The main contribution of this project is a general method for analyzing streaming lower bounds, rather than merely a collection of lower bound results. We hope to borrow ideas from information theory and cryptography, and develop systematic methods and tools for a better analysis of streaming lower bounds. The outcome of this project would be essential to a better understanding of the substance of streaming computation, and it will also provide new ideas and tools for the design and analyze stream algorithms.

自从上世纪90年代流式计算的概念被提出以来，流式计算模型中的下界问题一直是计算复杂性领域的重要研究方向。近年来，流式计算被广泛应用的同时也催生了很多变种模型，例如多读/写流模型、在线计算模型等，而传统的计算复杂度分析等下界方法在新的模型面前逐渐显得力不从心。.本项目计划通过对流式计算模型的下界分析方法的研究，加深对于流式计算的特点的理解、从而更有效地设计流式算法。本项目拟从三方面考虑：一是推广现有的多读/写流模型中基于信息论的下界分析方法；二是借鉴泄露容忍密码学中的思路证明流式算法的下界；三是研究通信复杂度与流式计算复杂度之间的关系并改进传统的下界证明方法。.本项目考虑的不是某几个问题的下界，而是希望从信息论和密码学引入新的思路，以全新角度研究流式计算中的下界，并构造通用的分析方法和理论工具。这对于揭示流式计算的本质具有重要意义，同时也必将为算法设计和分析提供崭新的思路和更为有利的工具。

项目进行期间，我们在不断加深理解流式计算的同时，改进了并构建出一套更精确、更具有普适性的流式计算下界分析方法。在多方计算单向通信的模型中，我们证明了对于定义在乘积分布上的对称函数，使用双方通信复杂度得出的流式计算下界至多有一个对数量级的损失，而对于定义在非乘积分布上的函数，由双方通信复杂度得到的下界可能与利用多方通信复杂度推出的下界有很大差距。具体来说，对于一个输入总长度为n的函数f，如果把f的输入划分成t份分给t个人，由他们共同计算函数f在该输入上的取值，本工作证明了以下两个结果。我们的第一个结果证明对于定义在乘积分布上的函数f，通信复杂度（相对于最坏划分下的双方通信复杂度）随人数增加的速度最快是Θ(tlogt)。这个关于通信复杂度随人数增长速度的上界是紧的，即对于任何函数f，由t个人共同计算时所需的通信复杂度都不超过双方通信复杂度的O(tlogt)倍，且存在一个函数f使得通信复杂度随人数增长的速度恰好是Θ(tlogt)。我们的第二个结果证明对于任意一个t，都存在定义域是非乘积分布的函数f，使得参与计算的人数低于阈值时所需的通信复杂度是O(t)的，而超过阈值时需要的通信复杂度是Ω(n)。如果t的取值是一个常数，则意味着由t人增加到t+1人时计算函数f所需的通信复杂度有一个从常数到n的线性量级的显著跃变。..本工作中的分析方法可直接用于证明流式计算的空间复杂度下界，例如对估计N维向量L0范数的流式算法可以证明一个紧的下界（Ω(ε^{−2} log(N) loglog(mM))）。此前最好的下界仅为Ω(ε^{−2} log(mM))。这个结果也可以直接区分用流式算法估计L0范数和Lp(p>1)范数的复杂度，因为后者有O(ε^{−2} log(mM))的上界。..运用上述工作的结论和分析方法，我们还证明了通过矩阵与向量的乘法来测试矩阵的性质时，采用左乘和右乘可能会有截然不同的结果。随着研究的深入，我们发现类似的分析方法还可以被用在字符串匹配、量子计算、社交网络等多个场景。