Diskretnaya Matematika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskretnaya Matematika, 2019, Volume 31, Issue 4, Pages 53–69
DOI: https://doi.org/10.4213/dm1585
(Mi dm1585)
 

This article is cited in 1 scientific paper (total in 1 paper)

Learning of monotone functions with single error correction

S. N. Selezneva, Y. Liu

Lomonosov Moscow State University, Faculty of Computational Mathematics and Cybernetics
Full-text PDF (489 kB) Citations (1)
References:
Abstract: Learning of monotone functions is a well-known problem. Results obtained by V. K. Korobkov and G. Hansel imply that the complexity $\varphi_M(n)$ of learning of monotone Boolean functions equals  $C_n^{\lfloor n/2\rfloor} + C_n^{\lfloor n/2\rfloor+1}$ ($\varphi_M(n)$ denotes the least number of queries on the value of an unknown monotone function on a given input sufficient to identify an arbitrary $n$-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.
Keywords: Boolean function, monotone function, learning of functions, learning complexity, $n$-dimensional Boolean cube, chain, chain partition, Hansel chains, error, error correction.
Funding agency Grant number
Russian Foundation for Basic Research 19-01-00200-а
Received: 22.07.2019
Revised: 07.11.2019
English version:
Discrete Mathematics and Applications, 2021, Volume 31, Issue 3, Pages 193–205
DOI: https://doi.org/10.1515/dma-2021-0017
Bibliographic databases:
Document Type: Article
UDC: 519.7
Language: Russian
Citation: S. N. Selezneva, Y. Liu, “Learning of monotone functions with single error correction”, Diskr. Mat., 31:4 (2019), 53–69; Discrete Math. Appl., 31:3 (2021), 193–205
Citation in format AMSBIB
\Bibitem{SelLiu19}
\by S.~N.~Selezneva, Y.~Liu
\paper Learning of monotone functions with single error correction
\jour Diskr. Mat.
\yr 2019
\vol 31
\issue 4
\pages 53--69
\mathnet{http://mi.mathnet.ru/dm1585}
\crossref{https://doi.org/10.4213/dm1585}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4043283}
\elib{https://elibrary.ru/item.asp?id=45517233}
\transl
\jour Discrete Math. Appl.
\yr 2021
\vol 31
\issue 3
\pages 193--205
\crossref{https://doi.org/10.1515/dma-2021-0017}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85114213894}
Linking options:
  • https://www.mathnet.ru/eng/dm1585
  • https://doi.org/10.4213/dm1585
  • https://www.mathnet.ru/eng/dm/v31/i4/p53
  • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретная математика
    Statistics & downloads:
    Abstract page:337
    Full-text PDF :32
    References:38
    First page:20
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024