This website uses features that are not well-supported by your browser. Please consider upgrading to a browser and version that fully supports CSS Grid and the CSS Flexible Box Layout Module.
Sidebar image
NB: A PDF version of this announcement (suitable for posting) is also available.

Information complexity: A paradigm for proving lower bounds

Amit Chakrabarti
Dartmouth College, Computer Science

Thursday, November 3, 2011
007 Kemeny Hall, 4 pm
Tea 3:30 pm, 300 Kemeny Hall

Abstract: A central question in lower bound theory is whether a compound (computational) problem that encodes N independent instances of a simple problem is N times as hard as the simple problem. Such a statement, when true, is called a direct sum theorem. Such theorems are not always easy to prove and sometimes, contrary to intuition, they are false!

In this talk, I shall describe a unified framework that I call the "information complexity paradigm" for proving various direct sum theorems. Central to the paradigm is a way to quantify the work of an algorithm (typically, a communication protocol) using information theoretic notions of entropy and mutual information, and then using mathematical properties of these quantities to analyze the algorithm.

I shall survey the large number of results that have made use of the paradigm, since its formal introduction at FOCS 2001. I shall briefly discuss the applications of such results, which range widely, touching upon high-dimensional nearest neighbor searching, algorithms for massive data streams, randomized decision trees, and Boolean circuits.

This talk will be accessible to graduate students.