Interactive information complexity and its applications (Yaqiao Li)

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

2019-05-13   14:00 ~ 15:00   

Speaker

Yaqiao Li, McGill university

Room

Room 602, School of Information Management & Engineering, Shanghai University of Finance & Economics