The Library
Learning circuits with few negations
Tools
Blais, Eric, Canonne, Clément L., Oliveira, Igor C., Servedio, Rocco A. and Tan, Li-Yang (2015) Learning circuits with few negations. In: International Workshop on Randomization and Computation (RANDOM), Princeton, NJ, USA., 24-26 Aug 2015. Published in: Leibniz International Proceedings in Informatics (LIPIcs), 40 pp. 512-527. doi:10.4230/LIPIcs.APPROX-RANDOM.2015.512 ISSN 1868-8969.
|
PDF
WRAP-learning-circuits-few-negations-Oliveira-2015.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (547Kb) | Preview |
Official URL: http://www.doi.org/10.4230/LIPIcs.APPROX-RANDOM.20...
Abstract
Monotone Boolean functions, and the monotone Boolean circuits that compute them, have been intensively studied in complexity theory. In this paper we study the structure of Boolean functions in terms of the minimum number of negations in any circuit computing them, a complexity measure that interpolates between monotone functions and the class of all functions. We study this generalization of monotonicity from the vantage point of learning theory, establishing nearly matching upper and lower bounds on the uniform-distribution learnability of circuits in terms of the number of negations they contain. Our upper bounds are based on a new structural characterization of negation-limited circuits that extends a classical result of A.A. Markov. Our lower bounds, which employ Fourier-analytic tools from hardness amplification, give new results even for circuits with no negations (i.e. monotone functions).
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Journal or Publication Title: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||
Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | ||||||
Place of Publication: | Dagstuhl, Germany | ||||||
ISSN: | 1868-8969 | ||||||
Official Date: | 2015 | ||||||
Dates: |
|
||||||
Volume: | 40 | ||||||
Page Range: | pp. 512-527 | ||||||
DOI: | 10.4230/LIPIcs.APPROX-RANDOM.2015.512 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Date of first compliant deposit: | 7 November 2019 | ||||||
Date of first compliant Open Access: | 7 November 2019 | ||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | International Workshop on Randomization and Computation (RANDOM) | ||||||
Type of Event: | Workshop | ||||||
Location of Event: | Princeton, NJ, USA. | ||||||
Date(s) of Event: | 24-26 Aug 2015 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year