Efficient and Private Property Testing via Indistinguishability

Cynthia Dwork, Pranay Tankala

Given a small random sample of $n$-bit strings labeled by an unknown Boolean function, which properties of this function can be tested computationally efficiently? We show an equiv…