The Non-Hardness of Approximating Circuit Size

Published in Theory of Computing Systems, 2020

Conference: CSR 2019. See the paper here: ECCC, CSR 2019 proceedings, journal version. Joint work with Eric Allender and Rahul Ilango.

This research was done at the 2018 DIMACS REU. Supported by NSF grants CCF-1514164 and CCF-1559855.