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.

Dartmouth College, Computer Science

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.