Learning of monotone functions with single error correctionстатья
Информация о цитировании статьи получена из
Web of Science
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 7 июля 2021 г.
Аннотация:Learning of monotone functions is a well-known problem. Results obtained by V. K. Korobkov and G. Hansel imply that the complexity f_𝑀(𝑛)of learning of monotone Boolean functions equals to 𝐶_n^{⌊𝑛/2⌋}+𝐶_n^{⌊𝑛/2⌋+1} (f_𝑀(𝑛) denotes the least number of queries on the value of an unknown monotone function on a given inputsufficient to identify an arbitrary𝑛-ary monotone function). In our paper we consider learning of monotone functions in the case when the teacher is allowed to return an incorrect response to at most one query on the value of an unknown function so that it is still possible to correctly identify the function. We show that learning complexity in case of the possibility of a single error is equal to the complexity in the situation when all responses are correct.