Previous Conferences & Workshops

Sep
24
2007

Computer Science/Discrete Mathematics Seminar I

Towards Universal Semantic Communiction
Madhu Sudan
11:15am|S-101

Is it possible for two intelligent players to communicate meaningfully with each other, without any prior common background? What does it even mean for the two players to understand each other? In addition to being an intriguing question in its own...

Sep
17
2007

Computer Science/Discrete Mathematics Seminar I

Algebrization: A New Barrier in Complexity Theory
11:15am|S-101

Any proof of P!=NP will have to overcome two barriers: relativization and natural proofs. Yet over the last decade, we have seen circuit lower bounds (for example, that PP does not have linear-size circuits) that overcome both barriers...

Sep
01
2007

Arithmetic Combinatorics

12:00am

Mini Conference December 10-12th

During term I of the year, School faculty member Jean Bourgain and Van Vu of Rutgers University led a program on arithmetic combinatorics. The following is preliminary information about the program.

Additive...

Jun
05
2007

Computer Science/Discrete Mathematics Seminar I

Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes
10:30am|S-101

The Fast Johnson-Lindenstrauss Transorm was recently discovered by Ailon and Chazelle as a technique for performing fast dimension reduction from $\ell_2^d$ to $\ell_2^k$ in time $O(\max\{d\log d, k^3\})$, where $k$ is the target lower dimension...