2005-2006 seminars

Using ideas from computational learning theory, I'll show that "for most practical purposes," one can learn a quantum state using a number of measurements that grows only linearly with the number of qubits n. By contrast, traditional quantum state...

In joint work with Yehuda Shalom, we have proved Margulis' Normal Subgroup Theorem for any discrete subgroup $\Gamma$ of the automorphism group of a locally finite $A_2$-tilde building, $B$, provided that the quotient of $B$ by $\Gamma$ is compact...

I will describe some recent results joint with V. Milman in which we take the computer science approach to derandomization and apply it in questions from asymptotic geometric analysis. The special type of questions requires an adaptation of the...

We show new connections between derandomization, worst-case hardness and average-case hardness. Specifically, we show that a mild derandomization assumption together with the worst-case hardness of NP implies the average-case hardness of a language...

Given the edge density $\rho$ of an undirected graph, what is the minimal possible density $g(\rho)$ of triangles in this graph? This is the quantitative version of the classical Turan theorem (41) that in the asymptotical form can be re-stated as...

Let $F$ be a family of graphs. A graph $H$ is *$F$-universal* if every $G\in F$ is isomorphic to a subgraph of $H$. Besides being of theoretical interest, universal graphs have applications in chip design and network simulation. For any two positive...

Let $G$ be a simple $G(\mathbf Q)$-group of $G(\mathbf Q)$-rank at least 2. In 1987 T. N. Venkataramana showed that if $\Gamma \subset G(\mathbf Z)$ is an infinite subgroup whose commensurator is a subgroup of finite index in $G(\mathbf Z)$, then $...

Given the edge density $\rho$ of an undirected graph, what is the minimal possible density $g(\rho)$ of triangles in this graph? This is the quantitative version of the classical Turan theorem (41) that in the asymptotical form can be re-stated as...

We'll begin with the following theorem, which proves a conjecture of S\'ark\"ozy, Selkow and Szemer\'edi, and try to use it as an excuse to talk about other things (perhaps including Br\'egman's Theorem, entropy, the ``incremental random method,"...

A pair (G,H), where G is a group and H a subgroup, has relative Property T if every isometric action of G on a Hilbert space has a H-fixed point. In a connected Lie group or a lattice G, we characterize subgroups H such that (G,H) has relative...