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.

Our commitment to inclusivity

Diversity and inclusivity are necessary partners. Without inclusivity, the benefits of diversity — an increase in understanding, improvement in performance, enhanced innovation, and heightened levels of satisfaction — will not be realized. We commit to investments in both, to create a community in which difference is valued, where each individual’s identity and contributions are treated with respect, and where differences lead to a strengthened identity for all. See Dartmouth College Inclusive Excellence Action Plan and Arts and Sciences Inclusive Excellence Reports.

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.