2005-2006 seminars

We shall discuss Quantum Computing, and the so called Hidden Subgroup Problem, which in the abelian case was the basis for Shor's celebrated factorization algorithm. The solution for non-abelian groups, and symmetric groups in particular, is one of...

Counting connected components and Betti numbers was a known technique in algebraic complexity theory in the late 1970's and early 1980's. Speculation arose as to whether such methods could attack lower bounds in Boolean complexity theory (e.g., P vs...

Paley graphs are well-known combinatorial objects which have many interesting properties. Many of these properties come from their symmetry under the automorphisms x-->ax+b of the affine line over a finite field F with q elements (q=4m+1). We...

A fundamental question in cryptography is whether the existence of hard on average problems can be based solely on the assumption that P not equal to NP (more precisely, NP not in BPP). The commonly held belief that average-case hardness requires...

We present a novel tree representation for the hard-core lattice gas model (weighted independent sets) on a general graph. We use this representation to show that for any graph of maximum degree D, the Gibbs measure is unique (the influence of any...

The classification of finite simple groups is widely acknowledged to be one of the major results in modern mathematics. The successful completion of its proof was announced in the early 1980's by Daniel Gorenstein. The original proof occupied...

Random matrices is a large area in mathematics, with connections to many other areas, such as mathematical physics, combinatorics, and theoretical computer sience, to mention a few. There are, by and large, two kinds of random matrices. The first...

Perhaps the most appealing conjectures in asymptotic convex geometry are (i) slicing (or isotropic constant) and (ii) variance. Together, they imply that for a random point X from an isotropic convex body in \R^n, the variance of |X|^2 is O(n). We...