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-01
• 期刊: Leibniz international proceedings in informatics
• 作者: Chen, Xue;Cheng, Kuan;Li, Xin;Ouyang, Minghui
• 通讯作者: Ouyang, Minghui

Improved Decoding of Expander Codes

改进的扩展码解码

• DOI: 10.1109/tit.2023.3239163
• 发表时间: 2023-06
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Chen, Xue;Cheng, Kuan;Li, Xin;Ouyang, Minghui
• 通讯作者: Ouyang, Minghui

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

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

• 发表时间: 2023-07
• 期刊: 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-07
• 期刊: Leibniz international proceedings in informatics
• 作者: Cheng, Kuan;Jin, Zhengzhong;Li, Xin;Wei, Zhide;Zheng, Yu
• 通讯作者: Zheng, Yu

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

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

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