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

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


Diskr. Mat., 2008, Volume 20, Issue 1, Pages 109–119 (Mi dm994)  

On complexity of linear operators on the class of circuits of depth 2

D. Yu. Cherukhin


Abstract: In this study we suggest methods for obtaining lower bounds for complexity of linear Boolean operators (and the related matrices) in two models of circuits of depth 2. In the first model, only linear elements with arbitrary number of inputs are allowed, whereas in the second one, any Boolean elements can be present. These methods are applicable to matrices with sufficiently large Hamming distance between the rows, for example, to the Hadamard matrices.

DOI: https://doi.org/10.4213/dm994

Full text: PDF file (151 kB)
References: PDF file   HTML file

English version:
Discrete Mathematics and Applications, 2008, 18:2, 143–154

Bibliographic databases:

UDC: 519.7
Received: 29.11.2005

Citation: D. Yu. Cherukhin, “On complexity of linear operators on the class of circuits of depth 2”, Diskr. Mat., 20:1 (2008), 109–119; Discrete Math. Appl., 18:2 (2008), 143–154

Citation in format AMSBIB
\Bibitem{Che08}
\by D.~Yu.~Cherukhin
\paper On complexity of linear operators on the class of circuits of depth~2
\jour Diskr. Mat.
\yr 2008
\vol 20
\issue 1
\pages 109--119
\mathnet{http://mi.mathnet.ru/dm994}
\crossref{https://doi.org/10.4213/dm994}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2420502}
\zmath{https://zbmath.org/?q=an:1172.94655}
\elib{http://elibrary.ru/item.asp?id=20730234}
\transl
\jour Discrete Math. Appl.
\yr 2008
\vol 18
\issue 2
\pages 143--154
\crossref{https://doi.org/10.1515/DMA.2008.011}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-44449088031}


Linking options:
  • http://mi.mathnet.ru/eng/dm994
  • https://doi.org/10.4213/dm994
  • http://mi.mathnet.ru/eng/dm/v20/i1/p109

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Дискретная математика
    Number of views:
    This page:289
    Full text:80
    References:21
    First page:5

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020