2009-2010 Seminars

In this talk we will present a near-optimal compression scheme for bounded-round randomized 2-party communication protocols. Previously, such a scheme was only known for protocols where the inputs to the parties are independent. The results yield a...

Semidefinite programming bounds are widely used in combinatorial optimization, quantum computing and complexity theory. The first semidefinite programming bound to gain fame is the so-called theta number developed by Lov\'asz to compute the Shannon...

We shall discuss new pseudorandom generators for regular read-once branching programs of small width. A branching program is regular if the in-degree of every vertex in it is (either 0 or) 2. For every width d and length n, the pseudorandom...

In this survey I will present several extremal problems, and some solutions, concerning convex lattice polytopes. A typical example is to determine the smallest area that a convex lattice polygon can have if it has exactly n vertices.

This talk will be concerned with how well can we approximate NP-hard problems. One of the most successful algorithmic strategies, from an upper bound perspective, is to write a polynomial time computable relaxation for an NP-hard problem and present...

For four years now, we have been conducting "medium-scale" experiments in how human subjects behave in strategic and economic settings mediated by an underlying network structure. We have explored a wide range of networks inspired by generative...