Abstract
The Minimum Circuit Size Problem (MCSP) asks whether a given Boolean function has a circuit of at most a given size. MCSP has been studied for over a halfcentury and has deep connections throughout theoretical computer science including to cryptography, computational learning theory, and proof complexity. For example, we know (informally) that if MCSP is easy to compute, then most cryptography can be broken. Despite this cryptographic hardness connection and extensive research, we still know relatively little about the hardness of MCSP unconditionally. Indeed, until very recently it was unknown whether MCSP can be computed in AC^0[2] (Golovnev et al., ICALP 2019).
Our main contribution in this paper is to formulate a new "oracle" variant of circuit complexity and prove that this problem is NPcomplete under randomized reductions. In more detail, we define the Minimum Oracle Circuit Size Problem (MOCSP) that takes as input the truth table of a Boolean function f, a size threshold s, and the truth table of an oracle Boolean function O, and determines whether there is a circuit with Ooracle gates and at most s wires that computes f. We prove that MOCSP is NPcomplete under randomized polynomialtime reductions.
We also extend the recent AC^0[p] lower bound against MCSP by Golovnev et al. to a lower bound against the circuit minimization problem for depthd formulas, (AC^0_d)MCSP. We view this result as primarily a technical contribution. In particular, our proof takes a radically different approach from prior MCSPrelated hardness results.
BibTeX  Entry
@InProceedings{ilango:LIPIcs:2020:11719,
author = {Rahul Ilango},
title = {{Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0[p]}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {34:134:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771344},
ISSN = {18688969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11719},
URN = {urn:nbn:de:0030drops117191},
doi = {10.4230/LIPIcs.ITCS.2020.34},
annote = {Keywords: Minimum Circuit Size Problem, reductions, NPcompleteness, circuit lower bounds}
}
Keywords: 

Minimum Circuit Size Problem, reductions, NPcompleteness, circuit lower bounds 
Seminar: 

11th Innovations in Theoretical Computer Science Conference (ITCS 2020) 
Issue Date: 

2020 
Date of publication: 

10.01.2020 