AF: EAGER: Data Streaming with a View towards Cloud Computing

高效处理大数据的能力正在成为现代生活的核心。越来越多的这种处理是在“云中”进行的，即在强大的服务器的大型集群上进行，这些服务器提供的计算能力远远超过弱客户端(例如，终端用户的个人计算机)上的可用计算能力。许多大数据问题需要对几乎不间断产生的海量数据流进行时空高效的处理：例如金融交易、医疗记录和科学实验数据。访问云计算服务使许多数据流问题变得容易处理，否则对于弱客户端来说是难以解决的。现有的云计算服务并不能保证客户端的计算将无错误地执行。在这个项目的过程中，PI将致力于设计和研究技术的理论基础，这些技术将使较弱的客户能够信任使用此类服务时所获得的结果。在该项目期间设计的新算法可能会对云计算和数据流系统的实践产生影响。该项目将使研究生和本科生能够在理论计算机科学研究和阐述方面进行培训，并在实验中学习与这种值得信赖的云计算相关的算法思想。该项目有两个主要线索。第一个是关于算法设计，其中PI将在上述弱客户端/强大服务器的设置下寻找新的或改进的算法(在空间使用和通信成本方面)。特别是，PI将重新讨论范数估计和聚类等基本问题。第二个线索是复杂性理论：PI将寻求理解这种计算设置的限制，很可能是通过证明通信复杂性的新下限。这一话题自然会引发关于亚瑟和梅林沟通的公开问题，这个话题长期以来一直被认为是一个足够困难的话题，即使是微小的进步也可能是重大突破。

The ability to efficiently and effectively process big data is becoming central to modern life. Increasingly, much of this processing takes place "in the cloud", on large clusters of powerful servers, which provide computational power far exceeding those available on a weak client, e.g., an end-user's personal computer. Many big data problems require time-and-space-efficient processing of massive data streams generated almost continuously: examples include financial transactions, medical records, and scientific experimentaldata. Access to a cloud computing service makes tractable a number of data streaming problems that would otherwise be intractable for a weak client.Existing cloud computing services do not give clients a guarantee that their computations will be executed error-free. In the course of this project, the PI will work to design and study the theoretical foundations of techniques that would enable a weak client to trust results arrived at when working withsuch a service. New algorithms designed during this project could have an impact on the practice of cloud computing and data streaming systems. The project will enable the training of graduate and undergraduate students in theoretical computer science research and exposition, and in experimentally studying algorithmic ideas relevant to such trustworthy cloud computing.The project has two major threads. The first is about algorithm design, wherein the PI will seek new or improved algorithms (in terms of space usage and communication costs) in the above weak-client/powerful-server setting. In particular, the PI will revisit such fundamental problems as norm estimation and clustering. The second thread is complexity-theoretic: the PI will seek to understand the limitations of this computational setting, most likely through proving new lower bounds in communication complexity. This thread naturally leads to open questions about Arthur-Merlin communication, a topic long known to be difficult enough that even small advances could be significant breakthroughs.