Competitive learning of monotone Boolean functions
classification
💻 cs.DS
cs.CCmath.OC
keywords
booleancompetitivemonotoneproblemalgorithmsanalysisapplybesides
read the original abstract
We apply competitive analysis onto the problem of minimizing the number of queries to an oracle to completely reconstruct a given monotone Boolean function. Besides lower and upper bounds on the competitivity we determine optimal deterministic online algorithms for the smallest problem instances.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.