2009-2010 Seminars

Mar
02
2010

Computer Science/Discrete Mathematics Seminar II

Computational Complexity and Information Asymmetry in Financial Products
10:30am|S-101

Collateralized Default Obligations (CDOs) and related financial derivatives have been at the center of the last financial crisis and subject of ongoing regulatory overhaul. Despite their demonstrable benefits in economic theory, derivatives suffer...

Mar
01
2010

Computer Science/Discrete Mathematics Seminar I

A Theory of Cryptographic Complexity
Manoj M. Prabhakaran
11:15am|S-101

In this talk, I shall describe an ongoing project to develop a complexity theory for cryptographic (multi-party computations. Different kinds of cryptographic computations involve different constraints on how information is accessed. Our goal is to...

Feb
23
2010

Computer Science/Discrete Mathematics Seminar II

Testing Correlations and Inverse Theorems
10:30am|S-101

The uniformity norms are defined in different contexts in order to distinguish the ``typical'' random functions, from the functions that contain certain structures. A typical random function has small uniformity norms, while a function with a non...

Feb
22
2010

Computer Science/Discrete Mathematics Seminar I

Average Sensitivity of Polynomial Threshold Functions
Rocco Servedio
11:15am|S-101

How many edges of the n-dimensional Boolean hypercube can be sliced by a degree-d polynomial surface? This question can be equivalently stated as "What is the maximum average sensitivity of any degree-d polynomial threshold function?" In 1994...

Feb
16
2010

Computer Science/Discrete Mathematics Seminar II

Complexity of Constraint Satisfaction problems: Exact and Approximate
Prasad Raghavendra
10:30am|S-101

Is there a common explanation for 2SAT being solvable polynomial time, and Max2SAT being approximable to a 0.91 factor? More generally, it is natural to wonder what characterizes the complexity of exact constraint satisfaction problems (CSP) like...

Feb
15
2010

Computer Science/Discrete Mathematics Seminar I

Graph Expansion and the Unique Games Conjecture
11:15am|S-101

The Unique Games Conjecture (Khot, 2002) is a central open question about hardness of approximation. In recent years, a sequence of works showed that the truth of this conjecture would have profound implications: If the conjecture is true, then...

Feb
09
2010

Computer Science/Discrete Mathematics Seminar II

Representation Theory and Expansion in Groups
10:30am|S-101

In this survey lecture (which will be continued), I plan to explain basic aspects of the representation theory of finite groups, and how these are applied to various questions regarding expansion and random walks on groups. These applications...

Feb
08
2010

Computer Science/Discrete Mathematics Seminar I

Interpreting Polynomial Structure Analytically
11:15am|S-101

I will be describing recent joint efforts with Tim Gowers to decompose a bounded function into a sum of polynomially structured phases and a uniform error, based on the recent inverse theorem for the U^k norms on F_p^n by Bergelson, Tao and Ziegler...

Feb
02
2010

Computer Science/Discrete Mathematics Seminar II

Representation Theory and Expansion in Groups
10:30am|S-101

In this survey lecture (which will continue on Tue., Feb 2) I plan to explain basic aspects of the representation theory of finite groups, and how these are applied to various questions regarding expansion and random walks on groups. These...