2004-2005 seminars

In a sequence of preprints M. Gromov introduced a new model of a random quotient of a finitely generated group and indicated that under favourable conditions the quotient groups should be non-trivial and satisfy Kazhdan's Property (T), both with...

The goal of Statistical Learning Theory is to construct and understand algorithms that are able to generalize from a given training data set. Statistical learning algorithms are wildly popular now due to their excellent performance on many types of...

The links between propositional proof systems and bounded arithmetic (a generic name for a collection of first-order theories of arithmetic) have many facets but informally one can view them as two sides of the same thing: The former is a non...

We derive a sufficient condition for a sparse graph G on n vertices to contain a copy of a tree T of maximum degree at most d on (1-\epsilon)n vertices, in terms of the expansion properties of G. As a result we show that for fixed d>=2 and 0

A classical method for proving geometric inequalities in which the Euclidean ball is the extremal case, is that of symmetrization. The idea is basically to perform a simple operation on a given convex body in n-dimensional space, which makes it more...

I will describe a connection between a classical inequality of Grothendieck and approximation algorithms based on semi-definite programming. The investigation of this connection suggests the definition of a new graph parameter, called the...

A graph property P is said to be uniformly-testable if there is a property-tester for P that receives the error parameter \epsilon as part of the input, and whose query complexity is a function of \epsilon only. P is said to be non-uniformly...

I want to show proofs for two things: (1) what kind of complicated structures can a player build in a "generalized Tic-Tac-Toe game", and (2) how to get the "exact solutions" of infinitely many games. I'll try to illustrate the ideas on simple...

We present new PCPs for NP-complete languages. The PCPs are only n poly log n bits long, when proving satisfiability of formulae of length n. However, the probabilistic verifier needs to query poly log n bits of the proof to verify it. In contrast...

Our main result is a reduction from worst-case lattice problems such as SVP and SIVP to a certain learning problem. This learning problem is a natural extension of the `learning from parity with error' problem to higher moduli. It can also be viewed...