2006-2007 seminars

Decomposition and modularity are fundamental issues in many fields, including mathematics, biology, engineering, and management. How can large systems be broken into subsystems which interact enough to meet the overall system goals, but not so much...

We investigate the complexity of the following polynomial solvability problem---given a finite field $\mathbb F_q$ and a set of polynomials $f_1, f_2, \dotsc, f_m \in \mathbb F_q[x_1, x_2, \dotsc, x_n]$ of total degree at most $d$, determine the...

We propose and discuss two conjectures on the nature of errors in highly correlated noisy physical stochastic systems. The first asserts that errors for a pair of substantially correlated elements are themselves substantially correlated. The second...

The main result of this work is an explicit disperser for two independent sources on $n$ bits, each of entropy $k=n^{o(1)}$. Put differently, setting $N=2^n$ and $K=2^k$, we construct explicit $N \times N$ Boolean matrices for which no $K \times K$...

The main result of this work is an explicit disperser for two independent sources on n bits, each of entropy k=n^{o(1)}. Put differently, setting N=2^n and K=2^k, we construct explicit N by N Boolean matrices for which no K by K submatrix is...

Combinatorial game theory is the study of combinations of two-player games with no hidden information and no chance elements. The subject has its roots in recreational mathematics, but in its modern form involves a rich interplay of ideas borrowed...

It is now well-known that a random walk on an expander graph is a very good "sampler", and this has been used to prove a variety of important results in complexity theory, cryptography and algorithms. On the surface, however, taking a walk on an...

Combinatorial game theory is the study of combinations of two-player games with no hidden information and no chance elements. The subject has its roots in recreational mathematics, but in its modern form involves a rich interplay of ideas borrowed...