In a previous blog post, we saw how ideas from differential privacy can be used to prove a lower bound on the hereditary discrepancy for the Erdös Discrepancy problem. This lower bound happened to be nearly tight. It turns out that this tightness is no accident. The connection between hereditary discrepancy and privacy is in … Continue reading From Discrepancy to Privacy, and back Part 2: Approximating Hereditary Discrepancy

Quick Reminder: the deadline for ICALP is Feb 15th. Time to rev up your latex engines. The call for papers is here.

I recently discovered that some colleagues are unaware of the math typesetting capabilities in PowerPoint, and so as a responsible Microsoft employee I thought it my duty to inform the public of these potentially time-saving and slides-beautifying features. This is also for my own benefit, as I seem to always forget where to find the … Continue reading Alt Equals

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