Fast and Robust Algorithms with Partial Data Access

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

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.