Hirahara, Shuichi ;
Oliveira, Igor C. ;
Santhanam, Rahul
NPhardness of Minimum Circuit Size Problem for ORANDMOD Circuits
Abstract
The Minimum Circuit Size Problem (MCSP) asks for the size of the smallest boolean circuit that computes a given truth table. It is a prominent problem in NP that is believed to be hard, but for which no proof of NPhardness has been found. A significant number of works have demonstrated the central role of this problem and its variations in diverse areas such as cryptography, derandomization, proof complexity, learning theory, and circuit lower bounds.
The NPhardness of computing the minimum numbers of terms in a DNF formula consistent with a given truth table was proved by W. Masek [William J. Masek, 1979] in 1979. In this work, we make the first progress in showing NPhardness for more expressive classes of circuits, and establish an analogous result for the MCSP problem for depth3 circuits of the form ORANDMOD_2. Our techniques extend to an NPhardness result for MOD_m gates at the bottom layer under inputs from (Z / m Z)^n.
BibTeX  Entry
@InProceedings{hirahara_et_al:LIPIcs:2018:8883,
author = {Shuichi Hirahara and Igor C. Oliveira and Rahul Santhanam},
title = {{NPhardness of Minimum Circuit Size Problem for ORANDMOD Circuits}},
booktitle = {33rd Computational Complexity Conference (CCC 2018)},
pages = {5:15:31},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770699},
ISSN = {18688969},
year = {2018},
volume = {102},
editor = {Rocco A. Servedio},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8883},
URN = {urn:nbn:de:0030drops88831},
doi = {10.4230/LIPIcs.CCC.2018.5},
annote = {Keywords: NPhardness, Minimum Circuit Size Problem, depth3 circuits}
}
2018
Keywords: 

NPhardness, Minimum Circuit Size Problem, depth3 circuits 
Seminar: 

33rd Computational Complexity Conference (CCC 2018)

Issue date: 

2018 
Date of publication: 

2018 