2004-2005 seminars

I will discuss some (very) recent results showing how techniques from the theory of Gaussian Hilbert spaces can be used in order to solve a number of open problems regarding boolean functions with low influences. I will survey some of the background...

We consider "local-update" Markov chains for sampling from independent sets and proper 3-colourings of a graph. An example of such a chain is the well-known Glauber dynamics, which updates the state of at most one vertex of the graph at each step...

A low-distortion embedding between two metric spaces is a mapping which preserves the distances between each pair of points, up to a small factor called distortion. Low-distortion embeddings have recently found numerous applications in computer...

In this talk, I'll present a new inequality which, for an arbitrary boolean function, relates the influence of its variables to decision tree computation of the function. Combining this with another inequality due to Schramm and Steif, we deduce new...

The main goal of this talk will be to present a proof of the following theorem. Theorem 1: For every fixed \delta >0 here is a polynomial time (in n = log N) computable function(s) f:[N]x[N]-->{0,1}, for which the following hold. For every two sets...

Ordinary 3-by-3 tic-tac-toe is trivial; the 3-dimensional 4-by-4-by-4 version is interesting but very complicated (first player wins; solved by Patashnik; heavy computer use); and the 5-by-5-by-5 version is already unsolved (expected to be a draw)...

A classical theorem of Edmonds provides a min-max formula relating the maximal size of a set in the intersection of two matroids to a ``covering" parameter. In this talk we generalize this theorem, replacing one of the matroids by a general...