Testing k-monotonicity. The rise and fall of Boolean functions

DOI10.4086/TOC.2019.V015A001MaRDI QIDQ5204819zbMATH OpenOpenAlexFDO

Authors Clement L. Canonne, Elena Grigorescu, Siyao Guo, A. Kumar, Karl Wimmer

Publication date 5 December 2019

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2019.v015a001

zbMATH Keywords

Boolean functionslearningmonotonicityproperty testing

Mathematics Subject Classification ID

Boolean functions (06E30) Networks and circuits as models of computation; circuit complexity (68Q06) Analysis of algorithms and problem complexity (68Q25) Computational learning theory (68Q32) Randomized algorithms (68W20)

Recommendations

• Testing k-monotonicity
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• An o(n) monotonicity tester for Boolean functions over the hypercube
• A \(o(n)\) monotonicity tester for Boolean functions over the hypercube

Cited in

(6)

• Testing k-monotonicity
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Sample-based distance-approximation for subsequence-freeness
• Nearly optimal bounds for sample-based testing and learning of k-monotone functions
• Let's try to be more tolerant: on tolerant property testing and distance approximation (invited talk)

This page was built for publication: Testing \(k\)-monotonicity. The rise and fall of Boolean functions

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