## Computational Complexity and Information Asymmetry in Financial Products

Collateralized Default Obligations (CDOs) and related financial derivatives have been at the center of the last financial crisis and subject of ongoing regulatory overhaul.

Boaz Barak

Princeton University

March 2, 2010

Collateralized Default Obligations (CDOs) and related financial derivatives have been at the center of the last financial crisis and subject of ongoing regulatory overhaul.

Manoj M. Prabhakaran

University of Illinois at Urbana-Champaign

March 1, 2010

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 qualitatively -- and if possible, quantitatively -- characterize the "cryptographic complexity" (defined using appropriate notions of reductions) of these different modes of accessing information. Also, we explore the relationship between such cryptographic complexity and computational intractability.

Charanjit Jutla

IBM T. J. Watson Research Center

February 28, 2010

Hamed Hatami

Institute for Advanced Study/Princeton University

February 23, 2010

Rocco Servedio

Columbia University

February 22, 2010

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 Gotsman and Linial posed this question and gave a conjectured answer: the symmetric function slicing the middle d layers of the Boolean hypercube has the highest average sensitivity of all degree-d polynomial threshold functions.

Prasad Raghavendra

University of Washington

February 16, 2010

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 2SAT and what determines the approximation ratios for MaxCSPs like Max2SAT.

Julia Wolf

Rutgers, The State University of New Jersey

February 8, 2010

Hoi H. Nguyen

Rutgers, The State University of New Jersey

February 1, 2010

Let η_{1}, . . . , η_{n} be iid Bernoulli random variables, taking values 1, −1 with probability 1/2. Given a multiset V of n integers v_{1}, . . . , v_{n}, we define the concentration probability as ρ(V ) := sup_{x} P(v_{1}η_{1} + · · · + v_{n}η_{n} = x).

Avi Wigderson

Institute for Advanced Study

January 26, 2010

Oded Schwartz

Technical University Berlin

January 25, 2010

Algorithms spend time on performing arithmetic computations, but often more on moving data, between the levels of a memory hierarchy and between parallel computing entities. Judging by the hardware evolution of the last few decades, the fraction of running time spent on communication is expected to increase, and with it - the demand for communication-avoiding algorithms. We use geometric, combinatorial, and algebraic ideas and techniques, some of which are known in the context of expander graphs, to construct provably communication-optimal algorithms.