The Library
NP-hardness of minimum circuit size problem for OR-AND-MOD circuits
Tools
Tools
Tools
Hirahara, Shuichi, Oliveira, Igor C. and Santhanam, Rahul (2018) NP-hardness of minimum circuit size problem for OR-AND-MOD circuits. In: Computational Complexity Conference, San Diego, California, 22-24 Jun 2018. Published in: Proceedings of the 33rd Computational Complexity Conference, 102 5:1-5:31. ISBN 9783959770699. ISSN 1868-8969. doi:10.4230/LIPIcs.CCC.2018.5
|
PDF
WRAP-NP-hardness-minimum-circuit-size-problem-OR-AND-MOD-circuits-Oliveira-2018.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (705Kb) | Preview |
Official URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2018.5
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 NP-hardness 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 NP-hardness of computing the minimum numbers of terms in a DNF formula consistent with a given truth table was proved by W. Masek [31] in 1979. In this work, we make the first progress in showing NP-hardness for more expressive classes of circuits, and establish an analogous result for the MCSP problem for depth-3 circuits of the form OR-AND-MOD2. Our techniques extend to an NP-hardness result for MODm gates at the bottom layer under inputs from (Z/mZ)n.
| Item Type: | Conference Item (Paper) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | |||||||||
| Divisions: | Faculty of Science > Computer Science | |||||||||
| Library of Congress Subject Headings (LCSH): | Computational complexity, Algebra, Boolean, NP-complete problems | |||||||||
| Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | |||||||||
| Journal or Publication Title: | Proceedings of the 33rd Computational Complexity Conference | |||||||||
| Publisher: | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik | |||||||||
| ISBN: | 9783959770699 | |||||||||
| ISSN: | 1868-8969 | |||||||||
| Official Date: | 2018 | |||||||||
| Dates: |
|
|||||||||
| Date of first compliant deposit: | 11 November 2019 | |||||||||
| Volume: | 102 | |||||||||
| Page Range: | 5:1-5:31 | |||||||||
| Article Number: | 5 | |||||||||
| DOI: | 10.4230/LIPIcs.CCC.2018.5 | |||||||||
| Status: | Peer Reviewed | |||||||||
| Publication Status: | Published | |||||||||
| Access rights to Published version: | Open Access | |||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||
| Conference Paper Type: | Paper | |||||||||
| Title of Event: | Computational Complexity Conference | |||||||||
| Type of Event: | Conference | |||||||||
| Location of Event: | San Diego, California | |||||||||
| Date(s) of Event: | 22-24 Jun 2018 | |||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
