Video Lectures

The basic problem of all pictures is grounded in their bipolar existence. They are created objects, but nonetheless present themselves as physical beings. This paradoxical double-structure is exemplified in the “ME FECIT” of numberless inscriptions...

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...

Humanitarianism, which can be defined as the introduction of moral sentiments into human affairs, is a major component of contemporary politics—locally and globally—for the relief of poverty or the management of disasters, in times of peace as well...

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...

Painter Alex Katz and his son, writer Vincent Katz, discuss their personal experiences in artistic collaboration in a conversation with Derek Bermel, the Institute's Artist-in-Residence. Both Alex and Vincent have been involved in numerous...

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...