Identification of partial disjunction, parity, and threshold functions

DOI10.1016/S0304-3975(99)00154-1MaRDI QIDQ1978506zbMATH OpenOpenAlexWikidataFDO

Authors Yanyan Li

Publication date 4 June 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(99)00154-1

zbMATH Keywords

Attribute-efficient learningComplexity of Boolean functionsRandomization

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Review text

Let F be a class of functions obtained by replacing some inputs of a Boolean function of a fixed type with some constants. The problem considered in this paper, which is called attribute efficient learning, is to identify ``efficiently a Boolean function g out of F by asking for the value of g at chosen inputs, where ``efficiency is measured in terms of the number of essential variables. We study the query complexity of attribute-efficient learning for three function classes that are, respectively, obtained from disjunction, parity, and threshold functions. In many cases, we obtain almost optimal upper and lower bound on the number of queries.

Recommendations

• Adaptive versus nonadaptive attribute-efficient learning
• scientific article; zbMATH DE number 1775448
• Learning counting functions with queries
• On parallel attribute-efficient learning.
• scientific article; zbMATH DE number 1617283

Cites work

• Attribute-efficient learning in query and mistake-bound models
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 4057247 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 3209689 (Why is no real title available?)
• Linear-size constant-depth polylog-threshold circuits
• Optimal depth, very small size circuits for symmetric functions in \(AC^ 0\)
• Queries and concept learning
• Randomized vs. deterministic decision tree complexity for read-once Boolean functions

Cited in

(1)

• Revising threshold functions

This page was built for publication: Identification of partial disjunction, parity, and threshold functions

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