Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > NEEKON VAFA:
All reports by Author Neekon Vafa:

TR18-173 | 17th October 2018
Eric Allender, Rahul Ilango, Neekon Vafa

The Non-Hardness of Approximating Circuit Size

Revisions: 1

The Minimum Circuit Size Problem (MCSP) has been the focus of intense study recently; MCSP is hard for SZK under rather powerful reductions, and is provably not hard under “local” reductions computable in TIME($n^{0.49}$). The question of whether MCSP is NP-hard (or indeed, hard even for small subclasses of P) ... more >>>




ISSN 1433-8092 | Imprint