1. <li id="egwb6"></li>

      <div id="egwb6"><span id="egwb6"><u id="egwb6"></u></span></div>
      <div id="egwb6"><strike id="egwb6"><kbd id="egwb6"></kbd></strike></div>

      <thead id="egwb6"></thead>

          1. 2019-05-13 | Yaqiao Li:Interactive information complexity and its applications

            2019-05-13   

            Abstract

            Information theory was introduced to study communication complexity in the past two decades. As a result, an independent topic called interactive information complexity has emerged in theoretical computer science. Given a Boolean function f: {0,1}^n times {0,1}^nto {0,1} where the input is subject to some prior distribution, information complexity studies how much information must be revealed in order to compute f in the classical Yao’s communication model. Intuitively, allowing some error in computing f could potentially reduce the amount of revealed information. In this talk, I will present my recent work that systematically studies the dependency of information complexity on the error allowed in computing Boolean functions, and its applications in both communication complexity and information complexity.

             

            Part of this talk is based on a joint work with Yuval Dagan, Yuval Filmus, and Hamed Hatami.

             

            Time

            5月13日周一)14:00-15:00

             

            Speaker

            Yaqiao Li is currently a PhD student in the school of computer science at McGill university. His recent main research interests are communication complexity and information complexity, and he is also interested in combinatorics, machine learning and decision science. Before coming to McGill, he finished his master study in pure mathematics at Peking University and bachelor study in computer science and technology at East China university of Science and Technology. He will join university of Montreal for a postdoc for the year 2019-2020. 

             

            Venue

            信息管理与工程学院602室

            上海财经大学(第三教学楼西侧)

            上海市杨浦区武东路100号