Monday, November 26, 2012

Differential privacy videos online!

Have you always wanted to learn about differential privacy, but haven't had the time/motivation to read all of the papers? Do you have 3 hours to kill? Well you are in luck! There are now 3 excellent tutorial videos online for you to enjoy! These are from the DIMACS workshop that Adam Smith and I ran last month.

  1. Moritz Hardt gives a tutorial on multiplicative weights in differential privacy:
  2. Gerome Miklau gives a tutorial on the matrix mechanism and related work in differential privacy:
  3. Benjamin Pierce gives a tutorial on differentially private programming languages:
  4. I give a tutorial on game theory and differential privacy:

These tutorials all assume some familiarity with differential privacy (I don't think differential privacy is actually -defined- in any of them). For some light reading to fill in some of the background, you can check out my course notes.

Monday, September 24, 2012

The Fifth Annual New York Computer Science and Economics Day

Are you going to be near NYC in December? The fifth annual New York Computer Science and Economics Day will be held in the new Simons Foundation auditorium in NYC on Monday, December 3rd. The theme for this year is "The Economics of Big Data, Information, and Privacy". In addition to a terrific lineup of invited speakers, posters and short talks (up to 10 minutes long) are invited from students. Abstracts for these should be submitted by November 5th. (Conveniently, right after the STOC deadline). 

See the website for more information: nyce1212

Friday, September 14, 2012

DIMACS Workshop on Differential Privacy and Call for Student Participation

Adam Smith and I are running a 3 day interdisciplinary workshop on differential privacy at DIMACS (Rutgers), on October 24-26. This is immediately following FOCS, which is also being held at Rutgers. The workshop will begin with a day of tutorials on differential privacy as understood in various communities (Theory, databases, programming languages, and game theory), and will continue with two days of research talks and discussion. Details of the workshop can be found here: We have an extremely exciting program. (The program listed on the website is somewhat out of date -- there are a half dozen or so additional speakers confirmed).

As part of the program, we will also have a session of short (5-10 minute) talks from students, postdocs, and other interested parties. We encourage submission of abstracts for short talks. The solicitation is below.

See you all in October!

DIMACS Workshop on Differential Privacy across Computer Science
October 24-26, 2012
(immediately after FOCS 2012)

Call for Abstracts -- Short Presentations

The upcoming DIMACS workshop on differential privacy will feature
invited talks by experts from a range of areas in computer science as
well as short talks (5 to 10 minutes) by participants.

Participants interested in giving a short presentation should send an
email to containing a proposed talk title,
abstract, and the speaker's name and affiliation.  We wil try to
accommodate as many speakers as possible, but
a) requests received before October 1 will get full consideration
b) priority will be given to junior researchers, so students and
postdocs should indicate their status in the email.

More information about the workshop:

The last few years have seen an explosion of results concerning
differential privacy across many distinct but overlapping communities
in computer science: Theoretical Computer Science, Databases,
Programming Languages, Machine Learning, Data Mining, Security, and
Cryptography. Each of these different areas has different priorities
and techniques, and despite very similar interests, motivations, and
choice of problems, it has become difficult to keep track of this
large literature across so many different venues. The purpose of this
workshop is to bring researchers in differential privacy across all of
these communities together under one roof to discuss recent results
and synchronize our understanding of the field. The first day of the
workshop will include tutorials, representing a broad cross-section of
research across fields. The remaining days will be devoted to talks on
the exciting recent results in differential privacy across
communities, discussion and formation of interesting open problems,
and directions for potential inter-community collaborations.

A tentative program and registration information can be found at

Friday, February 17, 2012

Amazing new declassified document

Its been a long time since I've posted on this blog, but along comes a great opportunity. Michael Kearns (tipped off by Ron Rivest) pointed me to a document this morning:

What this is, is a recently declassified correspondence between John Nash and the NSA from January 1955. In it, John Nash makes the distinction between polynomial time and exponential time, conjectures that there are problems that -cannot- be solved faster than in exponential time, and uses this conjecture as the basis on which  the security of a cryptosystem (of his own design) relies. He also anticipates that proving complexity lower bounds is a difficult mathematical problem:

"The nature of this conjecture is such that I cannot prove it, even for a special type of cipher. Nor do I expect it to be proven. But this does not destroy its significance. The probability of the truth of the conjecture can be guessed at on the basis of experiencing with enciphering and deciphering"

These letters predate even Godel's letter to Von Neumann, which goes into much less detail about complexity, and yet has also been taken to anticipate complexity theory and the P vs. NP problem.

Finally, an amusing aspect of this document is that it contains the NSA's internal notes on the correspondence. After a page or so of explanation as to why they are rejecting Nash's proposed system, they include the following offhand remark before finishing:

"An interesting pamphlet on Non-Cooperative Games, written by Mr. Nash was also sent to this Agency by the author for our information."