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, 2016, Volume 28, Issue 2, Pages 108–116
DOI: https://doi.org/10.4213/dm1373
(Mi dm1373)
 

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

Upper bounds for the size and the depth of formulae for MOD-functions

I. S. Sergeev

Research Institute "Kvant"
Full-text PDF (506 kB) Citations (1)
References:
Abstract: We obtain new upper bounds for the size and the depth of formulae for some MOD-functions (that is, functions counting $n$ bits modulo $m$). In particular, the depth of counting $n$ bits modulo $3$ is bounded by $2.8\log_2 n+O(1)$ in the standard basis $\{ \wedge, \vee, \overline{\phantom{a}} \}$; the size of counting modulo $5$ is bounded by $O(n^{3.22})$ in the same basis; the depth of counting modulo $7$ is bounded by $2.93\log_2 n+O(1)$ in the basis of all binary Boolean functions.
Keywords: symmetric Boolean function, depth, formula size.
Funding agency Grant number
Russian Foundation for Basic Research 14-01-00671а.
Research was supported by RBRF, project № 14-01-00671a.
Received: 26.09.2015
English version:
Discrete Mathematics and Applications, 2017, Volume 27, Issue 1, Pages 15–22
DOI: https://doi.org/10.1515/dma-2017-0003
Bibliographic databases:
Document Type: Article
UDC: 519.714.7
Language: Russian
Citation: I. S. Sergeev, “Upper bounds for the size and the depth of formulae for MOD-functions”, Diskr. Mat., 28:2 (2016), 108–116; Discrete Math. Appl., 27:1 (2017), 15–22
Citation in format AMSBIB
\Bibitem{Ser16}
\by I.~S.~Sergeev
\paper Upper bounds for the size and the depth of formulae for MOD-functions
\jour Diskr. Mat.
\yr 2016
\vol 28
\issue 2
\pages 108--116
\mathnet{http://mi.mathnet.ru/dm1373}
\crossref{https://doi.org/10.4213/dm1373}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3559796}
\elib{https://elibrary.ru/item.asp?id=26414207}
\transl
\jour Discrete Math. Appl.
\yr 2017
\vol 27
\issue 1
\pages 15--22
\crossref{https://doi.org/10.1515/dma-2017-0003}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000403470400003}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85016993219}
Linking options:
  • https://www.mathnet.ru/eng/dm1373
  • https://doi.org/10.4213/dm1373
  • https://www.mathnet.ru/eng/dm/v28/i2/p108
  • 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
    Дискретная математика
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024