The Minimum Formula Size Problem is (ETH) Hard.

Rahul Ilango

Browse the full FOCS paper archive.