SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle.

Rahul Ilango

Browse the full FOCS paper archive.