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

点击翻译按钮获取中文摘要

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.