Previous Conferences & Workshops

Nov
01
2004

Computer Science/Discrete Mathematics Seminar I

Influences and Decision Tree Complexity
11:15am|S-101

In this talk, I'll present a new inequality which, for an arbitrary boolean function, relates the influence of its variables to decision tree computation of the function. Combining this with another inequality due to Schramm and Steif, we deduce new...

Oct
28
2004

Informal Seminar

Limits on Efficient Computation in the Physical World
Scot Aaronson
4:00pm|S-101

I'll try to explain what we currently understand about the theoretical power of quantum computers, in a way that's accessible to a general math and physics audience. In particular, I'll demolish the popularly-held belief that quantum computing means...

Oct
26
2004

Special Statistical Mechanics Seminar

Tug of War and the Infinity Laplacian
4:00pm|S-101

The infinity Laplacian (informally, the "second derivative in the gradient direction") is a simple yet mysterious operator with many applications. "Tug of war" is a two player random turn game played as follows: SETUP: Assign each player one of two...

Oct
26
2004

Computer Science/Discrete Mathematics Seminar II

Explicit Constructions of Bipartite Ramsey Graphs
Boaz Barak and Guy Kindler
10:30am|S-101

The main goal of this talk will be to present a proof of the following theorem. Theorem 1: For every fixed \delta >0 here is a polynomial time (in n = log N) computable function(s) f:[N]x[N]-->{0,1}, for which the following hold. For every two sets...

Oct
25
2004

Joint IAS/Princeton University Number Theory Seminar

Real Zeros and Size of Rankin-Selberg L-functions in the Level Aspect
Guillaume Ricotta
4:30pm|Fine Hall 322

In 2002, J.B. Conrey and K. Soundararajan showed that there are infinitely many Dirichlet $L$-functions which do not vanish on the critical segment. Let $\mathcal{G}$ be the family of Dirichlet $L$-functions they considered. Following their work, a...

Oct
25
2004

Computer Science/Discrete Mathematics Seminar I

Tic-Tac-Toe Games: Exact Values of Infinitely Many Game Numbers
Jozsef Beck
11:15am|S-101

Ordinary 3-by-3 tic-tac-toe is trivial; the 3-dimensional 4-by-4-by-4 version is interesting but very complicated (first player wins; solved by Patashnik; heavy computer use); and the 5-by-5-by-5 version is already unsolved (expected to be a draw)...