CCSI Weekly Seminar: Bounded Indistinguishability for Low-Complexity Sources

Braverman’s theorem states that polylog(n) independent distributions over n bits fool all polynomial-size constant-depth AND/OR circuits (AC0).  In contrast, there exist √n-indistinguishable pairs of distributions (distributions on n bits whose projections on all size-√n subsets match) that cannot even fool the OR function.

Motivated by cryptographic applications, we ask whether Braverman-style results can be recovered for simple pairs of distributions, such as ones samplable by low-degree F2 polynomials.  We show that (1) For every d and ε there is a k such that all degree-d k-indistinguishable pairs ε-fool the OR function and (2) If all degree-1 o(n/polylog n)-indistinguishable pairs fool AC0 then the “Inner Product by AC0 over Parities” conjecture of Servedio and Viola must be true.

The results are from joint work with Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, and Akshayaram Srinivasan.