License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.512
URN: urn:nbn:de:0030-drops-53214
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5321/
Go to the corresponding LIPIcs Volume Portal

Blais, Eric ; Canonne, Clément L. ; Oliveira, Igor C. ; Servedio, Rocco A. ; Tan, Li-Yang

Learning Circuits with few Negations

pdf-format:
31.pdf (0.5 MB)

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

BibTeX - Entry

@InProceedings{blais_et_al:LIPIcs:2015:5321,
  author =	{Eric Blais and Cl{\'e}ment L. Canonne and Igor C. Oliveira and Rocco A. Servedio and Li-Yang Tan},
  title =	{{Learning Circuits with few Negations}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{512--527},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5321},
  URN =		{urn:nbn:de:0030-drops-53214},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.512},
  annote =	{Keywords: Boolean functions, monotonicity, negations, PAC learning}
}

Keywords: Boolean functions, monotonicity, negations, PAC learning
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Issue Date: 2015
Date of publication: 13.08.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI