## Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Progress

Michael Forbes

Massachusetts Institute of Technology

November 26, 2012

Michael Forbes

Massachusetts Institute of Technology

November 26, 2012

Daniel Licata

Carnegie Mellon University; Member, School of Mathematics

November 26, 2012

This talk is designed for a general mathematical audience; no prior knowledge of type theory is presumed.

Jing Chen

Massachusetts Institute of Technology; Member, School of Mathematics

November 27, 2012

Vladimir Voevodsky

Institute for Advanced Study

November 28, 2012

Alexander Beilinson

University of Chicago

November 28, 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

Israel M. Sigal

University of Toronto

November 30, 2012

Peter Dybjer

November 30, 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).