2008-2009 Seminars

It has been checked, for zillions of even numbers, that they can all be expressed as a sum of two primes. It has also been checked for zillions of (non-trivial) zeros of Zeta(s), that their real parts are all equal to one half. Alas, these checks do...

On Feb. 1, in his blog, Tim Gowers proposed an open collaboration on a math problem. Specifically, he suggested working on a combinatorial proof of the Density Hales-Jewett Theorem. This theorem states that for every delta > 0, if n is sufficiently...

In this talk, we will discuss how the circle method can be used to count solutions to Diophantine problems. After a brief overview of the circle method's history and applications, we will sketch how to prove an asymptotic for the number of integer...

I will present a construction of an n-point negative type metric such that every t-point sub-metric is isometrically L1-embeddable, but embedding the whole metric into L1 incurs distortion at least k, where both t and k are (\log\log\log n)^{\Omega...

The list decoding problem consists of finding the list of all codewords that differ from an input string (the received word) in at most a certain fraction of positions (equal to the target error-correction radius). Informally, the list decoding...

We prove lower bounds on the randomized two-party communication complexity of functions that arise from read-once boolean formulae. A read-once boolean formula F is a propositional formula in which each variable appears exactly once. Such a formula...

Via four applications: distribution modeling, probability estimation, data compression, and classification, we argue that when learning from data, discrete values should be ignored except for just their appearance-order pattern. Along the way, we...

Planarity is a central theme in graph theory and combinatorial geometry, dating back to Euler. There are many beautiful characterizations of planar graphs such as Kuratowski's forbidden minor theorem and Koebe's circle packing theorem from the 1930s...

I will discuss a lower bound of $\omega(n^(k/4))$ on the size of constant-depth $(AC_0)$ circuits solving the k-clique problem on n-vertex graphs. This bound follows from a stronger result that $AC_0$ circuits of size $O(n^(k/4))$ almost surely fail...