Learning circuits with few negations

DOI10.4230/LIPIcs.APPROX-RANDOM.2015.512zbMath1375.68063arXiv1410.8420OpenAlexW2963754417MaRDI QIDQ5351920

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

Publication date: 31 August 2017

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

zbMATH Keywords

monotonicityBoolean functionsnegationsPAC learning

Mathematics Subject Classification ID

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

Related Items

Alternation, sparsity and sensitivity: bounds and exponential gaps ⋮ On Negation Complexity of Injections, Surjections and Collision-Resistance in Cryptography ⋮ On the Complexity of Multivalued Logic Functions over Some Infinite Basis ⋮ Lower bounds for Boolean circuits of bounded negation width ⋮ Asymptotics of growth for non-monotone complexity of multi-valued logic function systems ⋮ Unnamed Item ⋮ The minimum number of negations in circuits for systems of multi-valued functions ⋮ Negation-limited formulas ⋮ Lower Bounds for DeMorgan Circuits of Bounded Negation Width ⋮ Exact value of the nonmonotone complexity of Boolean functions ⋮ Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity ⋮ Unnamed Item