To get announcements of talks and other events in the center, please sign up for our mailing list.
See the following pages for talks in partner institutions: Princeton, IAS, Rutgers, NYU

November 6th Center Meeting

[ November 6, 2009; 10:00 am to 3:15 pm. ] The Novermber 6 Center Meeting will be held in Room 402 of the Princeton Computer Science building. The schedule is given below:

10:00 – 10:45 Administrative meeting (Only for the Principal Investigators).

10:45 – 12:00 Madhur Tulsiani (abstract below)
12:00 – 1:15 Lunch + coffee break
1:15 – 2:15 Open Problems Session: Russell Impagliazzo, Valentine
Kabanets, Moni Naor, Mohan Paturi, [...]

Dieter van Melkebeek at theory lunch, Oct 30

[ October 30, 2009; 11:45 am to 1:15 pm. ] Theory lunch talk, Friday October 30:

Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses

Dieter van Melkebeek, University of Wisconsin Madison

Abstract. Consider the following two-player communication process to decide a language $L$: The first player holds the entire input $x$ but is polynomially bounded; the second player is computationally unbounded but does not know any part of $x$; their [...]

Mihai Patrascu at theory lunch, Oct 23

[ October 23, 2009; 12:00 pm to 1:00 pm. ] Towards Polynomial Lower Bounds for Dynamic Problems

Mihai Patrascu, AT&T Labs – Research

Moritz Hardt at Theory Lunch

[ October 16, 2009; 12:00 pm to 1:00 pm. ] Theory lunch talk: Friday October 16th.

On the Geometry of Differential Privacy

Moritz Hardt, Princeton University

Abstract:
We consider the noise complexity of differentially private mechanisms in the setting where the user asks d linear queries f:R^n->R non-adaptively. Here, the database is represented by a vector in R^n. Proximity between databases is measured in the l1-metric.

We show that the [...]

“Natural Algorithms” Workshop

[ November 2, 2009 to November 3, 2009. ] Nov2-Nov3, Princeton. The workshop will explore the benefits of viewing self-organizing systems, especially those occurring in nature, as “algorithms.” It will examine the possibility of building new bridges between theoretical computer science and the fields of biology, control theory, physics, engineering, and applied math, where dynamical systems have been traditionally studied.

Monthly Center Meeting, September 18

Schedule:
10:00 – 10:30 —- PI Meeting
10:30 – 12:00 —- Guy Rothblum (See abstract below)
12:00 Lunch is served
1:45 – 2:00 — Announcements.
2:00 – 2:25 — Troy Lee short talk.
2:25 – 2:50 —- Robert Tarjan short talk.
Abstract for Guy Rothblum:
Title:
On the Computational Complexity of Privacy-Preserving Data Analysis
In this talk we will consider privacy-preserving data analysis in the
setting [...]

Program, “Natural Algorithms” Workshop

Click here for registration form
Monday Nov.2
09:15-10:00 – Breakfast
10:00-10:30 – Devavrat Shah, “Belief Propagation and Combinatorial Optimization”
10:30-11:00 – Jorge Cortes, “Distributed wombling by robotic sensor networks”
11:00-11:30 – Break
11:30-12:00 – Leah Edelstein-Keshet,  “Group constraints on foraging”
12:00-12:30 – Tanya Berger-Wolf, “Finding structure in dynamic social networks”
12:30-2:00 Lunch
2:00-2:30 – Magnus Egerstedt, “Cooperative Foraging Among Bottlenose Dolphins and [...]

Tutorial on Limits of Approximation Algorithms: PCPs and Unique Games

The Center for Computational Intractability and DIMACS are co-sponsoring a tutorial on Limits of Approximation Algorithms, July 20-21, 2009. More details here.

Program for workshop on Impagliazzo’s Worlds

Tentative program for the workshop on
“Complexity and Cryptography: Status of Impagliazzo’s Worlds”
June 3-5, Princeton
Talks are in Room 006 in the Friend center , lunch and rump session in convocation room of Friend center, banquet is in Palmer House.
Parking: You can park in lots 3 and 21 using this permit, see  campus map . There are [...]

Videos for Geometry and Algorithms workshop

We’ve now posted online all the videos from the October workshop on geometry and algorithms. You can access the videos from the workshop’s program page.

Ketan Mulmuley on Algebraic Geometry and P vs NP

Ketan Mulmuley from the university of Chicago gave a sequence of 3 lectures in Mon-Wed Feb 9-11 in the IAS on his algebraic-geometric approach to the P vs NP problem. Videos of the talks can be found here: http://video.ias.edu/csdm/pvsnp
Ketan has promised to write scribe notes as well, which will be posted to the site above [...]

CS Colloquium: Eva Tardos on “Games in Networks: the price of anarchy and learning”

video: hi-res low-res
Title: Games in Networks: the price of anarchy and learning
Abstract:
Network games play a fundamental role in understanding behavior in many domains, ranging from communication networks through markets to social networks. Such networks are used, and also evolve due to selfish behavior of the users and owners. In light of these competing forces, it [...]

Theory Lunch: Satyen Kale on “Noise Tolerance of Expanders and Sublinear Expander Reconstruction”

video: hi-res low-res
Title: Noise Tolerance of Expanders and Sublinear Expander Reconstruction
Speaker: Satyen Kale, MSR New England
Abstract:
We consider the problem of online sublinear expander reconstruction and
its relation to random walks in “noisy” expanders. Given access to an
adjacency list representation of a bounded-degree graph G, we want to convert
this graph into a bounded-degree expander G’ changing G [...]

Theory Lunch: Avrim Blum on “A computational theory of clustering”

video: hi-res low-res
Title: A computational theory of clustering
Speaker: Avrim Blum, CMU
Abstract:
Problems of clustering data come up in many different areas throughout
science. Theoretical treatments of clustering have generally been of
two types: either on algorithms for (approximately) optimizing various
distance-based objectives such as k-median, k-means, and min-sum, or
on clustering under probabilistic “generative model” assumptions such
as mixtures of [...]

Center Meeting, Nov 7, 2008

THIRD INTRACTABILITY CENTER MONTHLY MEETING
Friday November 7, 2008, CS Dept, Princeton U [...]

10:00-10:30
Private PI meeting + Coffee for all
10:30-11:00
Adi Akavia: “Deterministically and Locally Finding Significant Fourier Transform Coefficients”
videos: hi-res, low-res, (older version)
11:00-11:30
Virginia Vassilevska: ” Matrix Products and All Pairs Path Problems”
videos: hi-res, low-res, (older version)
11:30-Noon
Open problems and announcements
Noon-1:00
Lunch
1:00-2:00
Breakout sessions
2:00-3:30
Sanjeev Arora and Moses Charikar: “Semidefinite programming [...]