For four years now, we have been conducting "medium-scale"
experiments in how human subjects behave in strategic and economic
settings mediated by an underlying network structure. We have
explored a wide range of networks inspired by generative...
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...
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...
We prove completeness results for certain class of functions
which have implications for automatic proving of
universally-composable security theorems for ideal and real
functionalities composed of if-then-else programs with (uniform)
random number...
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...
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...
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...
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 Uk norms on Fpn by Bergelson, Tao and Ziegler...