2007-2008 seminars

We will study the following problem: Given $n$ subsets $A_1, A_2,\ldots, A_n\subset \mathbb{F}_q$ of a finite field $\mathbb{F}_q$ with $q$ elements. Let $|A_1|\cdot |A_2|\cdot\ldots dot|A_n|>q^{1+\varepsilon}$ for some $\varepsilon>0,$ one needs to...

An important task in systematic biology is the reconstruction of phylogenies: The evolutionary history of a family of organisms, represented by an evolutionary tree, needs to be reconstructed from the genetic data of the extant species, which...

A graph separator is a set of edges whose deletion partitions the graph into two (or more) pieces. Finding small graph separators is a fundamental combinatorial problem with numerous applications. Interest in it also derives from its theoretical...

Let $G$ be a finite Abelian group, say $Z/NZ$. A set $\Lambda = \{ lambda_1, \dots, \lambda_{m} \}$ is called {\it dissociated} if any equality $\sum_{i=1}^m \varepsilon_i \lambda_i = 0$, where $\varepsilon_i \in \{ 0,\pm 1 \}$ implies that all $...

The computation of Nash equilibria has been a problem that spanned half a century that has attracted Economists, Operations Researchers, and most Recently, Computer Scientists. Intuitively, the complexity of a game grows along a few axes: the number...

I will present a result that shows hardness of weak PAC-learning intersection of two halfspaces using a hypothesis which is an intersection of k halfspaces for any (fixed) integer k. Specifically, for every integer k and an arbitrarily small...

In this talk, we discuss a new technique which shows how to find a copy of a sparse bipartite graph in a graph of positive density. Our results imply several new bounds for classical problems in Ramsey theory and improve and generalize earlier...

A network creation game abstracts a network construction by selfish agent who build a network by buying links to each other. Each player pays a fixed cost per link, and suffers an additional communication cost (which is the sum of distances to the...

The aim is to present some of the more technical aspects of my joint project with Tim Gowers regarding the true complexity of a system of linear quations. Using so-called "quadratic Fourier analysis", we determined a necessary and sufficient...