Supersimulators

Cynthia Dwork, Pranay Tankala

We prove that every randomized Boolean function admits a supersimulator: a randomized polynomial-size circuit whose output on random inputs cannot be efficiently distinguished from…