AF: Medium: The Trace Reconstruction Problem

AF：中：迹线重建问题

• 批准号: 2106429
• 负责人: Rocco Servedio
• 金额: $ 120万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-06-01 至 2025-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2106429&HistoricalAwards=false
• 关键词: AF; Medium; Trace; Reconstruction; Problem

Problems that involve the transmission and recovery of information play an important role in computer science and many related areas. For example, the field of coding theory studies how to cleverly encode a message so that the underlying information can still be recovered even after the message has been subjected to some kind of corruption by noise. While coding theory has been hugely successful and influential, there are many real-world settings in which a noise process affects information "in the wild" where coding schemes cannot be applied. For example, given a DNA sequence that is subject to mutations or deletions, there is no opportunity to encode the sequence using tools of coding theory because it occurs in nature in a way that is not under human control. So, there is a need for techniques that can reconstruct information that has *not* been cleverly encoded, and yet has been corrupted with different types of noise. One particularly challenging type of noise is "deletion noise", meaning that some of the characters of the message are deleted with no indication being given as to where the deletions took place. Fortunately, in many scenarios of this sort it is natural to assume that multiple independent copies of the deletion-plagued data are available; for example, in a biological setting one might have many copies of a given DNA sequence where deletions have affected each copy in a different way. This project will study algorithms for performing reconstruction in scenarios such as the above. Another important goal of this project will be dissemination and outreach activities. Planned activities include new advanced courses on reconstruction problems, training graduate students and postdocs through research collaboration, disseminating research results through seminar talks, survey articles and other publications, and continuing ongoing outreach activities aimed at increasing interest in and awareness of theoretical computer science in a broader population.In more detail, the research team will build on their preliminary results to develop new algorithms for the trace-reconstruction problem, where independent copies of data corrupted by deletions (such a deletion-corrupted data string is known as a "trace") are available and the challenge is to reconstruct the original uncorrupted data. They will analyze a number of different natural variants of this problem, which are obtained by making different assumptions about the nature of the deletion process (low, intermediate, or high deletion rates, correlated versus uncorrelated deletions, and so on); the type of data that is being transmitted (worst-case data, average-case data, etc); and the desiderata for successful reconstruction (perfect reconstruction versus different notions of approximate reconstruction). The research team will also investigate new algorithmic problems related to deletion noise, including more challenging versions of the problem described above in which the reconstruction algorithm is given a mixture of traces from multiple different source strings and the goal is to reconstruct the entire underlying "population" of source strings rather than just a single source string.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序列，就没有机会使用编码理论工具来编码该序列，因为它在自然界中以不受人类控制的方式发生。 因此，需要一种能够重建尚未被巧妙编码但已被不同类型的噪声破坏的信息的技术。 一种特别具有挑战性的噪声类型是“删除噪声”，这意味着消息的某些字符被删除，但没有给出删除发生在何处的指示。 幸运的是，在许多此类场景中，很自然地假设存在删除问题的数据的多个独立副本可用。例如，在生物环境中，一个给定的 DNA 序列可能有许多拷贝，其中删除以不同的方式影响每个拷贝。 该项目将研究在上述场景中执行重建的算法。 该项目的另一个重要目标是传播和外展活动。计划的活动包括关于重建问题的新高级课程、通过研究合作培训研究生和博士后、通过研讨会演讲、调查文章和其他出版物传播研究成果，以及继续开展旨在提高人们对理论计算机科学的兴趣和认识的外展活动。更详细地说，研究团队将在他们的初步结果的基础上开发用于痕迹重建问题的新算法，其中被删除损坏的数据的独立副本（这样的删除损坏的数据字符串被称为“痕迹”） ）可用挑战是重建原始的未损坏的数据。他们将分析该问题的许多不同的自然变体，这些变体是通过对删除过程的性质做出不同的假设而获得的（低、中或高删除率、相关删除与不相关删除等）；正在传输的数据类型（最坏情况数据、平均情况数据等）；以及成功重建的需求（完美重建与近似重建的不同概念）。 研究团队还将研究与删除噪声相关的新算法问题，包括上述问题的更具挑战性的版本，其中重建算法被赋予来自多个不同源字符串的痕迹的混合，目标是重建整个底层“群体” “源字符串而不仅仅是单个源字符串。该奖项反映了 NSF 的法定使命，并且通过使用基金会的智力优点和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Approximate Trace Reconstruction from a Single Trace

从单个迹线进行近似迹线重建

• 发表时间: 2023-01
• 期刊: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA
• 作者: Chen, Xi;De, Anindya;Lee, Chin Ho;Servedio, Rocco A.;Sinha, Sandip
• 通讯作者: Sinha, Sandip

Subset Sum in Time 2^{n/2}/poly(n)

时间子集和 2^{n/2}/poly(n)

• DOI: 10.4230/lipics.approx/random.2023.39
• 发表时间: 2023-01
• 期刊: and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023
• 作者: Chen, Xi;Jin, Yaonan;Randolph, Tim;Servedio, Rocco A.
• 通讯作者: Servedio, Rocco A.

On the complexity of dynamic submodular maximization

关于动态子模最大化的复杂性

• DOI: 10.1145/3519935.3519951
• 发表时间: 2022-01
• 期刊: Proceedings of the 54th ACM Symposium on Theory of Computing (STOC 22'
• 作者: Chen, Xi;Peng, Binghui
• 通讯作者: Peng, Binghui

Computational Hardness of the Hylland-Zeckhauser Scheme

Hylland-Zeckhauser 方案的计算难度

• DOI: 10.1137/1.9781611977073.90
• 发表时间: 2022-01
• 期刊: Annual ACM-SIAM Symposium on Discrete Algorithms
• 作者: Chen, Thomas;Chen, Xi;Peng, Binghui;Yannakakis, Mihalis
• 通讯作者: Yannakakis, Mihalis

Memory-Query Tradeoffs for Randomized Convex Optimization

随机凸优化的内存查询权衡

• DOI: 10.1109/focs57990.2023.00086
• 发表时间: 2023-06-21
• 期刊: 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: X. Chen;Binghui Peng
• 通讯作者: Binghui Peng