This post will be about differential privacy (DP), with a focus on what is often referred to in the differential privacy literature (often colloquially) as "privacy loss". A brief recap of the setting: a trusted data curator has a database of sensitive information about individuals. The curator wants to release aggregate statistical information about the … Continue reading Privacy Loss as a Random Variable

A typical computer science paper might represent the work of 2-4 authors over a year. Even though these authors don't spend 100% of that year working on the paper, just counting their salaries, benefits, etc.. we see that the total cost to produce a paper can still easily amount to several tens of thousands of … Continue reading Occupy ACM: We are the 99%

Computational learning is full of problems that are deceptively simple to state but fiendishly hard to solve. Perhaps none more so than the problem of learning Juntas, posed by Avrim Blum and Pat Langley. Its the kind of problem which seems well suited for a polymath endeavor, Dick Lipton likes to say that you could … Continue reading Learning Juntas

I continue the discussion from last post. We are trying to add unpredictability to tennis by looking for a monotone, transitive and balanced function $latex f$ such that $latex E_p(f)$ has a wide threshold window, that is, we want the range of $latex p$ where $latex E_p(f)$ is, say, between 0.01 and 0.99, to be as large … Continue reading Tennis for the People II

I love sports, at least watching it. I could be tempted to follow any competition in any sport (with the obvious exceptions of baseball, cricket and golf). Now that the London Olympic games are almost forgotten and the world cup a full year and a half away (576 days to be precise) I want to … Continue reading Tennis for the People

Due to the effects of Hurricane Sandy, the deadline for STOC 2013 has been extended to Monday, November 5, 5pm EST, see http://stoc.cs.yale.edu/stoc2013/ 

This is the season for academic job searches, and if you are looking for a postdoc in theoretical Computer Science, we hope you consider applying for a position at Microsoft Research. The various MSR labs are looking for postdocs in many scientific fields, including all areas of theoretical Computer Science. You can apply for postdoc … Continue reading Postdoc positions at MSR

The following message from Joan Feigenbaum describes some major changes in the new formatting requirements. While these changes may be controversial, it’s important to take note. --------------------- 1) Please read the Call for Papers carefully and pay special attention to length and formatting requirements, which have changed since last year: a) Submissions must be no … Continue reading Message from STOC 2013 PC Chair – Joan Feigenbaum

This post is about implementing cryptography with real objects—rods, chains, and locks—and it is going to be light on formulas and heavy on pictures. Fun! Many cryptographic schemes have real-world analogues, some less trivial than others. Digital signatures are the most obvious example, where the cryptographic scheme achieves pretty much the same task as traditional … Continue reading Cryptography in the Real World