2005-2006 seminars

Jul
11
2006

Special Computer Science/Discrete Mathematics Seminar I

The learnability of Quantum States
11:00am|S-101

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...

May
23
2006

Lie Groups, Representations and Discrete Mathematics

On Margulis' Normal Subgroup Theorem
2:00pm|West Building Lecture Theatre

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...

May
16
2006

Computer Science/Discrete Mathematics Seminar II

Randomness Reduction in Some Results of Asympotic Geometric Analysis
Shiri Artstein
10:30am|Dilworth Room

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...

May
15
2006

Computer Science/Discrete Mathematics Seminar I

New Connections Between Derandomization, Worst-Case Complexity and Average-Case Complexity
Danny Gutfreund
11:15am|Dilworth Room

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...

May
09
2006

Computer Science/Discrete Mathematics Seminar II

On the Minimal Density of Triangles in Graphs (continued)
10:30am|S-101

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...

May
08
2006

Computer Science/Discrete Mathematics Seminar I

Universal Graphs
11:15am|S-101

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...

May
02
2006

Lie Groups, Representations and Discrete Mathematics

Almost Normal Subgroups of Lattices
George Willis
2:00pm|S-101

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 $...

May
02
2006

Computer Science/Discrete Mathematics Seminar II

On the Minimal Density of Triangles in Graphs
10:30am|S-101

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...

May
01
2006

Computer Science/Discrete Mathematics Seminar I

Many Hamiltonian Cycles
Jeff Kahn
11:15am|S-101

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,"...

Apr
25
2006

Lie Groups, Representations and Discrete Mathematics

Relative Property T in Lie Groups and their Lattices
Yves de Cornulier
2:00pm|S-101

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...