Fast and Robust Algorithms with Partial Data Access

具有部分数据访问功能的快速、稳健的算法

• 批准号: 2228814
• 负责人: Elena Grigorescu
• 金额: $ 49.98万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-10-01 至 2025-09-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2228814&HistoricalAwards=false
• 关键词: Fast; Robust; Algorithms; Partial; Data

The demand for fast data handling is prevalent in the use of most new technologies and scientific endeavo­­rs, especially in autonomous systems, communication networks, healthcare, data storage systems, and economic and financial markets. Some of the challenges encountered often stem from the need to quickly recover data, or to quickly make irrevocable decisions, based only on partial information about the input. In addition, information symbols may be misaligned or may contain significant amounts of noise, because of either random physical processes, adversarial behavior, or human or machine errors. Thus, unrestricted access to clean data is often an unrealistic expectation, which leads to a pressing need for creative methods to fight these challenges. The project will address such challenges by developing novel techniques inspired from coding theory, learning theory and machine learning, as well as graph theory and optimization, to build and analyze desirable algorithmic solutions. The outcomes of the project have the potential to be deployed in DNA data storage technologies, communication systems, network systems, and settings in which machine learning may enhance algorithmic guarantees. The project will broaden participation in computing by actively involving in research both undergraduate students and underrepresented minorities. The research will be broadly disseminated through presentations in workshops, seminars, and conferences, and it will be integrated in undergraduate and graduate courses. The project will advance knowledge by developing efficient, robust, and reliable algorithms that can deal with misaligned or badly damaged data and algorithms that only have partial or restricted access to the data. The research will address three specific areas. First, it will focus on error-correcting codes that can withstand adversarial or random insertion and deletion errors, when the algorithm is given only a partial view of the data, namely in the setting of local decoding. Secondly, it will study data recovery in a particular learning model, namely when the noise damages the attributes of the data. Thirdly, it will focus on algorithms that can only access the data in an online fashion and must make irreversible decisions, both in classical settings as well as in settings where the algorithms may be enhanced with machine learning advice. The project aims to develop state-of-the-art tools and techniques to analyze limitations of current algorithmic techniques in the above models, and to propose adequate models that bypass such limitations.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.

在大多数新技术和科学努力的使用中，特别是在自治系统、通信网络、医疗保健、数据存储系统以及经济和金融市场中，对快速数据处理的需求是普遍存在的。遇到的一些挑战通常源于需要快速恢复数据，或仅基于有关输入的部分信息快速做出不可撤销的决策。此外，由于随机的物理过程、对抗行为或人为或机器错误，信息符号可能会不对齐或包含大量的噪声。因此，不受限制地访问干净数据往往是一个不切实际的期望，这导致迫切需要创造性的方法来应对这些挑战。该项目将通过开发受编码理论、学习理论和机器学习以及图论和优化启发的新技术来解决这些挑战，以构建和分析理想的算法解决方案。该项目的成果有可能部署在DNA数据存储技术、通信系统、网络系统以及机器学习可以增强算法保证的环境中。该项目将通过积极参与本科生和未被充分代表的少数群体的研究，扩大对计算机的参与。这项研究将通过讲习班、研讨会和会议的报告广泛传播，并将纳入本科和研究生课程。该项目将通过开发高效、稳健和可靠的算法来推进知识的发展，这些算法可以处理不对齐或严重损坏的数据，以及只能部分或限制访问数据的算法。这项研究将涉及三个具体领域。首先，它将专注于纠错码，可以承受对抗性或随机插入和删除错误，当算法只给出数据的部分视图时，即在局部解码的设置中。其次，它将研究特定学习模型下的数据恢复，即当噪声破坏数据的属性时。第三，它将专注于只能以在线方式访问数据的算法，并且必须做出不可逆转的决定，无论是在经典设置中，还是在算法可以通过机器学习建议增强的设置中。该项目旨在开发最先进的工具和技术来分析上述模型中当前算法技术的局限性，并提出绕过这些局限性的适当模型。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Approximation Algorithms for Directed Weighted Spanners

定向加权扳手的近似算法

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

On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors

关于汉明和插入删除错误的宽松本地可解码码

• 发表时间: 2023
• 期刊: Leibniz international proceedings in informatics
• 作者: Block, Alexander R.;Blocki, Jeremiah;Cheng, Kuan;Grigorescu, Elena;Li, Xin;Zheng, Yu;Zhu, Minshen
• 通讯作者: Zhu, Minshen

How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity

• DOI: 10.48550/arxiv.2210.03831
• 发表时间: 2022-10
• 作者: Jeremiah Blocki;Elena Grigorescu;Tamalika Mukherjee;Samson Zhou

Learning-Augmented Algorithms for Online Linear and Semidefinite Programming

• DOI: 10.48550/arxiv.2209.10614
• 发表时间: 2022-09
• 期刊: ArXiv
• 作者: Elena Grigorescu;Young-San Lin;Sandeep Silwal;Maoyuan Song;Samson Zhou