AF: Small: New Efficient Algorithms for Complex Data

AF：小：复杂数据的新高效算法

• 批准号: 1910411
• 负责人: Elena Grigorescu
• 金额: $ 26.81万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2023-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1910411&HistoricalAwards=false
• 关键词: AF; Small; New; Efficient; Algorithms

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.

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

项目成果

Hardness of Maximum Likelihood Learning of DPPs

• DOI: 10.48550/arxiv.2205.12377
• 发表时间: 2022-05
• 期刊: Electron. Colloquium Comput. Complex.
• 作者: Elena Grigorescu;Brendan Juba;K. Wimmer;Ning Xie

Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions

用于插入和删除的本地可解码和可纠正代码的指数下界

• DOI: 10.1109/focs52979.2021.00077
• 发表时间: 2022
• 期刊: IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS
• 作者: Blocki, Jeremiah;Cheng, Kuan;Grigorescu, Elena;Li, Xin;Zheng, Yu;Zhu, Minshen
• 通讯作者: Zhu, Minshen

Approximation Algorithms for Directed Weighted Spanners

定向加权扳手的近似算法

• 发表时间: 2023
• 期刊: Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik
• 作者: Grigorescu, Elena Kumar

Differentially-Private Sublinear-Time Clustering

差分隐私次线性时间聚类

• DOI: 10.1109/isit45174.2021.9518014
• 发表时间: 2021
• 期刊: Differentially-Private Sublinear-Time Clustering
• 作者: Blocki, Jeremiah;Grigorescu, Elena;Mukherjee, Tamalika
• 通讯作者: Mukherjee, Tamalika

Locally Decodable/Correctable Codes for Insertions and Deletions

用于插入和删除的本地可解码/可纠正代码

• DOI: 10.4230/lipics.fsttcs.2020.16
• 发表时间: 2020
• 期刊: 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
• 作者: Block, A;Blocki, J;Grigorescu, E;Kulkarni, S;Zhu, M.
• 通讯作者: Zhu, M.