## Type Systems

Vladimir Voevodsky

Professor, Institute for Advanced Study

December 5, 2012

Vladimir Voevodsky

Professor, Institute for Advanced Study

December 5, 2012

Ran Raz

Weizmann Institute; Member, School of Mathematics, IAS

December 4, 2012

Mark Braverman

Princeton University

December 3, 2012

In this talk we will discuss information complexity -- a measure of the amount of information Alice and Bob need to exchange to solve a problem over distributed inputs. We will present an information-theoretically optimal protocol for computing the AND of two bits distributed between Alice and Bob. We prove that the information complexity of AND is ~1.4923 bits. We use the optimal protocol and its properties to obtain tight bounds for the Disjointness problem, showing that the randomized communication complexity of Disjointness on n bits is ~0.4827n ± o(n).

Juerg Frohlich

ETH Zurich; Member, School of Mathematics, IAS

December 3, 2012

Israel M. Sigal

University of Toronto

November 30, 2012

Peter Dybjer

November 30, 2012

Chris Kapulkin

Visiting Student, School of Mathematics

November 29, 2012

Andrew Sutherland

Massachusetts Institute of Technology<a href="/webfm_send/5174">Sutherland-2012-11-29.lo.mp4</a>

November 29, 2012

Vladimir Voevodsky

Institute for Advanced Study

November 28, 2012

Alexander Beilinson

University of Chicago

November 28, 2012