Conference item icon

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 th...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Publisher's version

Actions


Access Document


Files:
Publisher copy:
10.4230/LIPIcs.CCC.2018.5

Authors


Hirahara, S More by this author
More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Oxford college:
Magdalen College
Publisher:
Schloss Dagstuhl Publisher's website
Volume:
102
Pages:
5:1--5:31
Series:
Leibniz International Proceedings in Informatics
Publication date:
2018-06-22
Acceptance date:
2018-04-05
DOI:
ISSN:
1868-896
Pubs id:
pubs:845746
URN:
uri:e231576d-a5f0-4119-bc1d-5aa8ef2a046f
UUID:
uuid:e231576d-a5f0-4119-bc1d-5aa8ef2a046f
Local pid:
pubs:845746
ISBN:
978-3-95977-069-9

Terms of use


Metrics



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

TO TOP