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). https://doi.org/10.1007/s00224-020-10004-x
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.