Algorithms and lower bounds for sublinear processing of long sequences and large data

随着越来越多的应用程序产生和存储大量数据，大数据的处理在许多领域变得至关重要。在这个建议中，我们感兴趣的是在存在资源限制的情况下处理大量数据。特别是，我们希望在属性测试、流和传感器网络聚合模型中开发算法，允许输入大小的时间和/或空间亚线性。显然，如此严格的限制意味着我们的算法提供的解决方案在许多情况下不能完全准确；我们的目标之一是探索这些模型中准确性和效率之间的权衡。我们将重点关注与序列性质相关的问题，但随着技术的发展，我们将探索其他领域。

As more and more applications are generating and storing massive amounts of data, the processing of large data is becoming crucial in many fields. In this proposal we are interested in processing large amounts of data in the presence of resource constraints. In particular, we would like to develop algorithms in the property testing, streaming, and sensor network aggregation models, allowing time and/or space sublinear in the size of the input. Clearly, such tight restrictions imply that the solutions provided by our algorithms cannot be fully accurate in many cases; one of our goals is to explore the tradeoff between accuracy and efficiency in these models. We will focus on problems related to properties of sequences, but will explore other areas as we develop more techniques.