欢迎访问江苏省计算机学会网站!    设为首页  |  收藏本站
江苏省计算机学会
  •  当前位置首页 > 新闻中心 > 通知公告
    新闻中心  
    党建工作
    学会动态
    政策法规
    行业新闻
    图片新闻
    通知公告
    学会通讯
     
    通知公告
    青年学者学术报告 《Efficient Document Exchange and Error Correcting Codes with Asymmetric Information》
    发布时间:2020-12-22 11:32:38

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

    摘 要:
    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.

    时间:12月25日(星期五) 10:00

    地点:计算机科学技术楼224室


    上一篇:青年学者学术沙龙《组合测试实践研究探索》
    下一篇:青年学者学术报告 《Machine Learning Assisted Network Slicing for Wireless Edge Computing System》
    友情链接:
    江苏省科学技术协会 中国计算机学会 南京大学 南京大学计算机科技与技术系 南京大学软件学院 东南大学计算机科学与工程学院 江苏经贸职业技术学院 南京信息职业技术学院 南京工业职业技术学院 江苏海事职业技术学院 常州信息职业技术学院 国网电力科学研究院 电子科技集团第28研究所 江南计算技术研究所 
       
     

    Copyright (c) 版权所有 江苏省计算机学会          南京网站建设公司
    秘书处办公室       地址: 江苏省南京市仙林大道163号  邮编:210023   电话/传真:025-89680909   
    秘书处市内联络点   地址: 江苏省南京市汉口路22号     邮编:210093   电话/传真:025-86635622
    电子邮箱:jscs@nju.edu.cn   网址:www.jscs.org.cn    技术支持:南京成旭通信息技术有限公司  

    网站备案号:苏ICP备14049275号-1

    您是本站第10477808位来客!

    在线客服

    点击这里给我发消息