Previous Conferences & Workshops

Feb
26
2008

Computer Science/Discrete Mathematics Seminar II

Sound 3-Query PCPPs Are Long
Arie Matsliah
10:30am|S-101

We present a tradeoff between the length of a 3-query probabilistically checkable proof of proximity (PCPP) and the best possible soundness obtained by querying it. Consider the task of distinguishing between "good" inputs w \in {0,1}^n that are...

Feb
25
2008

Computer Science/Discrete Mathematics Seminar I

Security Under Key-Dependent Inputs
Shai Halevi
11:15am|S-101

In this work we re-visit the question of building cryptographic primitives that remain secure even when queried on inputs that depend on the secret key. This was investigated by Black, Rogaway, and Shrimpton in the context of randomized encryption...

Feb
22
2008

Special Seminar

Introduction to Non-Abelian p-Adic Hodge Theory
10:30am|S-101

This is the first in a series of (probably) three talks whose goal is to understand Faltings’ paper "A p-adic Simpson correspondence". Roughly speaking, this is a correspondence between Higgs bundles over a smooth proper curve X over the field of p...

Feb
19
2008

Algebro-Geometric Derived Categories and Applications

D-Modules and Loop Spaces
2:00pm|S-101

Equivariant localization relates the geometry of a space to the geometry of the fixed points of a group action. A categorified application of this technique allows one to recover D-modules on a smooth space from coherent sheaves on its loop space...

Feb
19
2008

Computer Science/Discrete Mathematics Seminar II

New Results and Open Problems in Computing Nash Equilibria
Christos Papadimitriou
10:30am|S-101

In the past few years there has been much excitement, and many positive and negative results, regarding the computation of equilibria in games. The problem of finding Nash equilibria in games was shown intractable, there is an on-going race of...

Feb
18
2008

Computer Science/Discrete Mathematics Seminar I

Integrality Gaps for Sherali-Adams Relaxations
Yury Makarychev
11:15am|S-101

We prove strong lower bounds for Sherali-Adams relaxations of the MAX CUT, Vertex Cover and Sparsest Cut problems. Specifically, we show that the integrality gap of MAX CUT and Vertex Cover relaxations is 2-$\epsilon$ after n^delta rounds (where...

Feb
15
2008

Special Seminar

A Gentle Introduction to Derived Algebraic Geometry
10:30am|S-101

This will be a relaxed, very elementary introduction to the central ideas and applications of derived algebraic geometry. My objective is to describe the Artin-Lurie Representability Theorem, and to give a number of interesting examples.