Conference item

NP-hardness of minimum circuit size problem for OR-AND-MOD 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 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 25 gates at the bottom layer under inputs from (Z/mZ)n.

Publication status:: Published

Peer review status:: Peer reviewed

Actions

Email

Email this record

Send the bibliographic details of this record to your email address.

Your Email
Please enter the email address that the record information will be sent to.

-
Your message (optional)
Please add any additional information to be included within the email.
Cite

Cite this record

APA Style

Hirahara, S., Oliveira, I., & Santhanam, R. (2018). NP-hardness of minimum circuit size problem for OR-AND-MOD circuits. 33rd Computational Complexity Conference (CCC 2018), 102, 5:1–5:31.

MLA Style

Hirahara, S., et al. “NP-Hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits.” 33rd Computational Complexity Conference (CCC 2018), vol. 102, Schloss Dagstuhl, 2018, pp. 5:1–5:31.

Chicago Style

Hirahara, S, I Oliveira, and R Santhanam. 2018. “NP-Hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits.” In 33rd Computational Complexity Conference (CCC 2018), 102:5:1–5:31. Leibniz International Proceedings in Informatics. Schloss Dagstuhl.
Share
Print

Access Document

Files:: Santhanam et al, NP-hardness of minimum circuit size problem f...

(Preview, Version of record, pdf, 705.8KB, Terms of use)

Publisher copy:: 10.4230/LIPIcs.CCC.2018.5

Authors

+ Hirahara, S More by this author

Role:: Author

+ Oliveira, I More by this author

Institution:: University of Oxford
Division:: MPLS Division
Department:: Computer Science
Role:: Author

+ Santhanam, R More by this author

Institution:: University of Oxford
Division:: MPLS
Department:: Computer Science
Oxford college:: Magdalen College
Role:: Author

Publisher:: Schloss Dagstuhl
Host title:: 33rd Computational Complexity Conference (CCC 2018)
Journal:: 33rd Computational Complexity Conference (CCC 2018) More from this journal
Volume:: 102
Pages:: 5:1--5:31
Series:: Leibniz International Proceedings in Informatics
Publication date:: 2018-06-22
Acceptance date:: 2018-04-05
DOI:: 10.4230/LIPIcs.CCC.2018.5
ISSN:: 1868-896
ISBN:: 9783959770699

Keywords:: Minimum Circuit Size Problem

depth-3 circuits

NP-hardness
Pubs id:: pubs:845746
UUID:: uuid:e231576d-a5f0-4119-bc1d-5aa8ef2a046f
Local pid:: pubs:845746
Source identifiers:: 845746
Deposit date:: 2018-05-03

Terms of use

Copyright holder:: Hirahara et al
Copyright date:: 2018
Notes:: © Shuichi Hirahara, Igor C. Oliveira, and Rahul Santhanam;
licensed under Creative Commons License CC-BY

Licence:: CC Attribution (CC BY)

Views and Downloads

About views and downloads

If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP