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



            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.






            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.