Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

[img]
Preview
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

Request Changes to record.

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:
DateEvent
2018Published
8 April 2018Accepted
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:
Project/Grant IDRIOXX Funder NameFunder ID
JP16J06743Japan Science and Technology Agencyhttp://dx.doi.org/10.13039/501100002241
JP16J06743[JSPS] Japan Society for the Promotion of Sciencehttp://dx.doi.org/10.13039/501100001691
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:
  • Other Repository

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us