AF: Small: New Efficient Algorithms for Complex Data

该研究项目的目标是开发新的超高效、可靠和健壮的算法，以解决在掌握复杂数据方面出现的现代挑战。例如，要成功地使用自动驾驶汽车等技术创新，就必须协同并快速地处理可能是高维的、分布式的、错误的甚至不完整的数据。这项研究项目将通过为处于通信核心的问题开发新的理论基础-高效的分布式计算、编码和信息理论以及机器学习，来推动使用如此多样化的数据进行计算的最先进水平。该项目还将涉及研究生和本科生的研究和指导，其成果将通过研讨会、会议、在线场所和作为教材广泛传播。该项目将集中于四个具体目标。第一个是抽象全局和局部模型，这些模型捕捉与分布式计算、学习和测试以及纠错相关的真实世界数据。第二个目标是设计有效的算法，并证明这些模型的极限下界。第三个目标是说明结构和快速计算之间的相互作用，特别是在上述模型中。最后，该项目旨在开发既针对数据又统一的新型分析技术。这些目标很可能通过将数学和计算机科学的不同领域的见解结合起来实现，包括学习和编码理论、次线性算法、密码学、几何学、统计学和优化。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The goal of this research project is to develop new super-efficient, reliable, and robust algorithms solving modern challenges that arise in mastering complex data. For example, to successfully employ technological innovations such as autonomous vehicles it is necessary to synergistically and quickly operate with data that may be high-dimensional, distributed, erroneous, or even incomplete. This research project will advance the state of the art in computing with such diverse data by developing new theoretical foundations for problems that lie at the heart of communication-efficient distributed computation, coding and information theory, and machine learning. The project will also involve graduate and undergraduate student research and mentoring, and the results will achieve wide dissemination though workshops, conferences, online venues, and as teaching material.The project will focus on four specific goals. The first one consists in abstracting global and local models that capture real-world data pertinent to distributed computation, learning and testing, and error-correction. The second goal is to design efficient algorithms and demonstrate limiting lower bounds in these models. The third goal is to illuminate the interplay between structure and fast computation, especially in the models mentioned above. Finally, the project aims to develop novel analysis techniques that are both data-specific, as well as unifying. These goals will likely be achieved by bridging insights from diverse areas of mathematics and computer science, including learning and coding theory, sublinear algorithms, cryptography, geometry, statistics and optimizations.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.