Previous Conferences & Workshops

Sep
22
2009

Computer Science/Discrete Mathematics Seminar II

The Completeness of the Permanent
Amir Yehudayoff
10:30am|S-101

In his seminal work, Valiant defined algebraic analogs for the classes P and NP, which are known today as VP and VNP. He also showed that the permanent is VNP-complete (that is, the permanent is in VNP and any problem in VNP is reducible to it). We...

Sep
15
2009

Computer Science/Discrete Mathematics Seminar II

Affine Dispersers from Subspace Polynomials
Swastik Kopparty
10:30am|S-101

An affine disperser over F_2^n for sources of dimension d is a function f: F_2^n --> F_2 such that for any affine subspace S in F_2^n of dimension at least d, we have {f(s) : s in S} = F_2 . Affine dispersers have been considered in the context of...

Sep
14
2009

Computer Science/Discrete Mathematics Seminar I

Blackbox Polynomial Identity Testing for Depth 3 Circuits
Shubhangi Saraf
11:15am|S-101

I will talk about a recent work describing a deterministic polynomial time algorithm for blackbox identity testing for depth three circuits with bounded top fanin over the field of rational numbers. This resolves a question posed by Klivans and...

Sep
01
2009

Analytic Number Theory

12:00am

During the academic year of 2009-2010, Enrico Bombieri of the School and Peter Sarnak of Princeton University/Institute for Advanced Study led a program on analytic number theory.

The program had an emphasis on analytic aspects, and particular...