Learning circuits with few negations

DOI10.4230/LIPICS.APPROX-RANDOM.2015.512zbMATH Open1375.68063arXiv1410.8420OpenAlexW2963754417MaRDI QIDQ5351920FDOQ5351920

Authors: Eric Blais, Clement L. Canonne, Igor C. Oliveira, Li-Yang Tan, Rocco A. Servedio 

Publication date: 31 August 2017

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, giving near-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).

Full work available at URL: https://arxiv.org/abs/1410.8420

Recommendations

• Limiting negations in bounded-depth circuits: an extension of Markov's theorem
• Limiting Negations in Constant Depth Circuits
• Negation-limited circuit complexity of symmetric functions
• On the Fourier spectrum of monotone functions
• Algorithms and Computation

zbMATH Keywords

monotonicityBoolean functionsPAC learningnegations

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Analysis of algorithms and problem complexity (68Q25)

Cited In (16)

• Testing \(k\)-monotonicity
• Alternation, sparsity and sensitivity: bounds and exponential gaps
• Negation-limited formulas
• Learning a circuit by injecting values
• On negation complexity of injections, surjections and collision-resistance in cryptography
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• On the complexity of multivalued logic functions over some infinite basis
• Optimal cryptographic hardness of learning monotone functions
• Lower bounds for Boolean circuits of bounded negation width
• Asymptotics of growth for non-monotone complexity of multi-valued logic function systems
• The minimum number of negations in circuits for systems of multi-valued functions
• Testing distributional assumptions of learning algorithms
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Optimal Cryptographic Hardness of Learning Monotone Functions
• Lower Bounds for DeMorgan Circuits of Bounded Negation Width
• Exact value of the nonmonotone complexity of Boolean functions

This page was built for publication: Learning circuits with few negations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5351920)