The Non-Hardness of Approximating Circuit Size

Published in Theory of Computing Systems, 2020

Recommended citation: Allender, E., Ilango, R. & Vafa, N. The Non-hardness of Approximating Circuit Size. Theory Comput Syst (2020).

Conference: CSR 2019. See the paper here: ECCC, CSR 2019 proceedings, journal version.

The main result of this paper shows that super-constant approximations to the Minimum Circuit Size Problem (MCSP) are unconditionally not NP-hard under AC^0 many-one reductions. In particular, this differentiates MCSP from many candidate NP-complete problems.

This research was done at the 2018 DIMACS REU with Rahul Ilango under the supervision of Professor Eric Allender. Supported by NSF grants CCF-1514164 and CCF-1559855.