计算机软件新技术国家重点实验室

摘 要：
The talk is mainly about document exchange protocols and ECCs with asymmetric information.In a Document Exchange problem, two parties hold two strings, and one party tries to learn the other party's string through communication. Two important goals in this problem are to minimize the communication complexity, and to design efficient protocols.We focus on whether asymmetric partial information can help. The asymmetric partial information is modeled by one party having some prior knowledge that there are some subsets of positions s.t. errors only happen in these areas, but nowhere else. We provide efficient randomized constructions, with sketch length close to optimal and almost linear running time. We further use the above hamming distance version protocol to construct an efficient randomized protocol foredit distance. This improves the previous result by Haeupler (FOCS'19), Belazzougui and Zhang (FOCS'16). Our techniques are based on a generalization of the celebrated expander codes by Sipser and Spielman (FOCS'94), which may be of independent interests. Joint work with Xin Li (Johns Hopkins University).
报告人简介:
Kuan Cheng is an assistant professor at Center on Frontiers of Computing Studies, Peking University. Previously he did a postdoc at UT Austin. Before that he achieved a PhD degree from Johns Hopkins University, advised by Xin Li. His research interests are mainly about randomness and combinatorics in computation, and their applications in Complexity Theory, Information Theory. He is also interested in learning theory, networks and quantum computing, etc.