Recently Added

Complexity of Constraint Satisfaction Problems: Exact and Approximate

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.

Artistic Collaboration: A Conversation with Alex and Vincent Katz

Alex and Vincent Katz
February 12, 2010

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 collaborative projects.  Alex has collaborated on books with many poets, including John Ashbery, Robert Creeley, and Kenneth Koch, and he has designed sets and costumes for choreographers Paul Taylor and David Parsons.  Vincent has collaborated with the artists Rudy Burckhardt, Francesco Clemente, and Wayne Gonzales.  He is an art critic who has authored numerous essays and articles on contemporary artists; he is the publisher of the poetry journal Vanitas and of Libellum Books; and he serves as Chair of the Board of the Bowery Poetry Club.

The NOF Communication Complexity of Multiparty Pointer Jumping

Joshua Brody
Dartmouth College
December 7, 2009

We give new results on the number-on-the-forhead (NOF) communication complexity of the multiparty pointer jumping problem.
The origional motivation for this problem comes from circuit complexity. Specifically, there is no explicit function known to lie outside the complexity class ACC0. However, a long line of research in the early 90's showed that a sufficiently strong NOF communication lower bound for a function would place it outside ACC0. Pointer jumping is widely considered to be a strong candidate for such a lower bound.

The Completeness of the Permanent

Amir Yehudayoff
Institute for Advanced Study
October 6, 2009

In his seminal work, Valiant defined algebraic analogs for the classes P and NP, which are known today as VP and VNP. He also showed that the permanent is VNP-complete (that is, the permanent is in VNP and any problem in VNP is reducible to it). We will describe the ideas behind the proof of this completeness of the permanent.

An Algorithmic Proof of Forster's Lower Bound

Moritz Hardt
Princeton University
December 15, 2009

We give an algorithmic proof of Forster's Theorem, a fundamental result in communication complexity. Our proof is based on a geometric notion we call radial isotropic position which is related to the well-known isotropic position of a set of vectors. We point out an efficient algorithm to compute the radial isotropic position of a given set of vectors when it exists.

Algorithmic Dense Model Theorems, Decompositions, and Regularity Theorems

Russell Impagliazzo
Institute for Advanced Study
December 8, 2009

Green and Tao used the existence of a dense subset indistinguishable from the primes under certain tests from a certain class to prove the existence of arbitrarily long prime arithmetic progressions. Reingold, Trevisan, Tulsiani and Vadhan, and independently, Gowers, give a quantitatively improved characterization of when such dense models exist. An equivalent formulation was obtained earlier by Barak, Shaltiel and Wigderson.

Arithmetic Progressions in Primes

Madhur Tulsiani
Institute for Advanced Study
November 24, 2009

I will discuss the Green-Tao proof for existence of arbitrarily long arithmetic progressions in the primes. The focus will primarily be on the parts of the proof which are related to notions in complexity theory. In particular, I will try to describe in detail how the proof can be seen as applying Szemeredi's theorem to primes, by arguing that they are indistinguishable from dense subsets of integers, for a suitable family of distinguishers.