AF: Small: Fundamental Questions in Communication and Computation Regarding Edit Type String Measures

AF：小：有关编辑类型字符串测量的通信和计算的基本问题

• 批准号: 2127575
• 负责人: Xin Li
• 金额: $ 44.18万
• 依托单位: Johns Hopkins University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-10-01 至 2025-09-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2127575&HistoricalAwards=false
• 关键词: AF; Small; Fundamental; Questions; Communication

Strings are fundamental objects in many important computer scienceapplications, such as text/speech processing, bioinformatics, datastorage and access, and communication systems. However, processingstrings presents various challenges in computation and communication.For example, many of today's applications involving strings areimplemented on large data sets, and the known algorithms are often toocostly in both time and space. Similarly, when strings are transmittedbetween systems, errors like insertions and deletions occur frequently,which can lead to problems from a simple misunderstanding to a severesystem failure. These challenges are usually addressed by high costsolutions, where one either requires a large amount of resources for thealgorithms, or expensive hardware that keeps systems strictlysynchronized. The overarching goal of this project is to understand thefundamental question of how to more efficiently compute differentstring measures, and transmit strings reliably in the presence ofinsertions and deletions. This will lead to a deeper theoreticalunderstanding of the nature of various string measures and errors, aswell as potentially much more efficient solutions in practice. Examplesof benefits include algorithms that use much less resources for handlinglarge data sets, and more reliable communication systems in adversarialenvironments. The project also has plans for mentoring PhD students,integration of the research topics into courses taught to students froma variety of different backgrounds, and support of under-representedgroups of students in computer science.The project contains two sets of specific goals. The first set of goalsseeks to understand how to design efficient error-correcting codes forinsertions and deletions. These include codes and document-exchangeprotocols over the binary alphabet with asymptotically optimalparameters; codes that form a linear subspace or have a low densityparity check matrix, which allow fast encoding and decoding; listdecodable codes that can correct a larger fraction of errors withoutputting a small list of possibly correct messages; and locallydecodable codes that can correctly recover any target message bit withonly a few queries of the codeword. The second set of goals investigatesthe space complexity of various string measures, such as edit distance,longest common subsequence, and longest increasing subsequence.Specifically, the goal is to both design algorithms that require muchsmaller space to compute or approximate these string measures, and toprove better space lower bounds in various models. These two sets ofgoals are also naturally connected, since the codes in the first partcan often be used to give space lower bounds in the second part. Thestudy of these topics will be based on techniques from several differentareas such as probability theory, information theory, combinatorics,algorithm design, communication complexity, and pseudorandomness, andwill further foster the interactions among these areas towardsbreakthroughs.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的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Improved Decoding of Expander Codes

改进的扩展码解码

• DOI: 10.4230/lipics.itcs.2022.43
• 发表时间: 2022
• 期刊: Leibniz international proceedings in informatics
• 作者: Chen, Xue;Cheng, Kuan;Li, Xin;Ouyang, Minghui
• 通讯作者: Ouyang, Minghui

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

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

Linear Insertion Deletion Codes in the High-Noise and High-Rate Regimes

高噪声和高速率状态下的线性插入删除码

• 发表时间: 2023
• 期刊: Leibniz international proceedings in informatics
• 作者: Cheng, Kuan;Jin, Zhengzhong;Li, Xin;Wei, Zhide;Zheng, Yu
• 通讯作者: Zheng, Yu