Identification of partial disjunction, parity, and threshold functions
type: Item
instance of: scholarly article
title: Identification of partial disjunction, parity, and threshold functions
zbMATH Open document ID: 0947.68536
DOI: 10.1016/S0304-3975(99)00154-1
author: Yanyan Li
published in: Theoretical Computer Science
publication date: 2000-06-04T00:00:00Z
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.
Mathematics Subject Classification ID: 68Q32
zbMATH DE Number: 1454285
zbMATH Keywords: Complexity of Boolean functions
zbMATH Keywords: Attribute-efficient learning
zbMATH Keywords: Randomization
MaRDI profile type: Publication
cites work: Q3792452
cites work: Queries and concept learning
cites work: Attribute-efficient learning in query and mistake-bound models
cites work: Optimal depth, very small size circuits for symmetric functions in \(AC^ 0\)
cites work: Randomized vs. deterministic decision tree complexity for read-once Boolean functions
cites work: Q4856179
cites work: Q4231923
cites work: Q5336810
cites work: Linear-size constant-depth polylog-threshold circuits
cites work: Q3762226
Wikidata QID: Q127120407
full work available at URL: s0304-3975(99)00154-1
OpenAlex ID: W2024028777
description: scientific article; zbMATH DE number 1454285