## The Simplicial Model of Univalence

Peter Lumsdaine

Dalhousie University; Member, School of Mathematics, IAS

December 6, 2012

Peter Lumsdaine

Dalhousie University; Member, School of Mathematics, IAS

December 6, 2012

Vladimir Voevodsky

Professor, Institute for Advanced Study

December 5, 2012

Ran Raz

Weizmann Institute; Member, School of Mathematics, IAS

December 4, 2012

Juerg Frohlich

ETH Zurich; Member, School of Mathematics, IAS

December 3, 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).

Peter Dybjer

November 30, 2012

Israel M. Sigal

University of Toronto

November 30, 2012

Andrew Sutherland

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

November 29, 2012

Chris Kapulkin

Visiting Student, School of Mathematics

November 29, 2012

Alexander Beilinson

University of Chicago

November 28, 2012