We say that a function f\colon \Sigma^n \to \{0, 1\} is \epsilon-fooled by k-wise indistinguishability if f cannot distinguish with advantage \epsilon between any two distributions \mu and \nu over \Sigma^n whose projections to any k symbols are identical. We study the class of functions f that are fooled by ... more >>>

Prediction algorithms assign numbers to individuals that are popularly understood as individual ``probabilities''---what is the probability of 5-year survival after cancer diagnosis?---and which increasingly form the basis for life-altering decisions. Drawing on an understanding of computational indistinguishability developed in complexity theory and cryptography, we introduce Outcome Indistinguishability. Predictors that are ... more >>>

A pair of sources \mathbf{X},\mathbf{Y} over \{0,1\}^n are k-indistinguishable if their projections to any k coordinates are identically distributed. Can some \mathit{AC^0} function distinguish between two such sources when k is big, say k=n^{0.1}? Braverman's theorem (Commun. ACM 2011) implies a negative answer when \mathbf{X} is uniform, whereas Bogdanov et ... more >>>