Below are the 15 most recent events, see the archive for older posts
Women in Theory 2010 Workshop
[ June 19, 2010 to June 23, 2010. ] Women In Theory 2010
June 19-23, 2010 at Princeton University
Program chair: Tal Rabin.
Local co-chairs: Boaz Barak and Moses Charikar.
WomenInTheory2010 {at} gmail(.)com
(See also WIT 2008 home page and video from WIT 2008)
The ”’Women in Theory (WIT)”’ Workshop is intended for graduate and undergraduate students in the area of theory of computer science. The workshop will feature technical talks and [...]
John Watrous at theory lunch
[ November 13, 2009; 12:00 pm to 1:00 pm. ] Theory Lunch, Friday Nov 13, 2009
QIP = PSPACE
John Watrous, University of Waterloo
Abstract. The interactive proof system model of computation is a cornerstone of complexity theory, and its quantum computational variant has been a topic of study in quantum complexity theory for the past decade. In this talk I will present an exact characterization of the [...]
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 [...]
Pseudorandomness workshop at IAS June 14-18
[ June 14, 2010 to June 18, 2010. ] IAS is co-organizing with the center for computational intractability a workshop on
Pseudo-randomness in Mathematical Structures
on June 14-18.
Organizers: Jean Bourgain, Russell Impagliazzo, Peter Sarnak and Avi Wigderson
Email:pseudo.workshop {at} gmail(.)com
See http://www.math.ias.edu/pseudo2010 for more details.
Registration to the workshop is free, but we strongly request that people register before March 7, 2010.
We encourage participants to make their hotel reservation early by [...]
“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 [...]
Barriers workshop program updated
The program for the barriers workshop is now online. See also the main workshop webpage for more information about it.
Hope to see you in Princeton next week!
Barriers workshop program updated
The program for the barriers workshop is now online. See also the main workshop webpage for more information about it.
Hope to see you in Princeton next week!
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 [...]
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 [...]