Intelligent systems. Theory and applications
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Intelligent systems. Theory and applications:
Year:
Volume:
Issue:
Page:
Find






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


Intelligent systems. Theory and applications, 2021, Volume 25, Issue 5, Pages 55–74 (Mi ista326)  

The complexity of multilayer $d$-dimensional circuits

T. Sitdikova, G. V. Kalachevb

a Google LLC
b Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Problems of Theorecical Cybernetics Lab
References:
Abstract: In this paper we research a model of multilayer circuits with a single logical layer. We consider $\lambda$-separable graphs as a support for circuits. We establish the Shannon function lower bound $\max ( \frac{2^n}{n}, \frac{2^n (1 - \lambda)}{\log k})$ for this type of circuits where k is the number of layers. For d-dimensional graphs, which are $\lambda$-separable for $\lambda = \frac{d-1}{d}$, this gives the Shannon function lower bound $\frac{2^n}{\min(n, d \log k)}$. For multidimensional rectangular circuits the proved lower bound asymptotically matches to the upper bound.
Keywords: multilayer circuits, multidimensional circuits, Shannon function asymptotics, circuit complexity, graph separators.
Document Type: Article
Language: English
Citation: T. Sitdikov, G. V. Kalachev, “The complexity of multilayer $d$-dimensional circuits”, Intelligent systems. Theory and applications, 25:5 (2021), 55–74
Citation in format AMSBIB
\Bibitem{SitKal21}
\by T.~Sitdikov, G.~V.~Kalachev
\paper The complexity of multilayer $d$-dimensional circuits
\jour Intelligent systems. Theory and applications
\yr 2021
\vol 25
\issue 5
\pages 55--74
\mathnet{http://mi.mathnet.ru/ista326}
Linking options:
  • https://www.mathnet.ru/eng/ista326
  • https://www.mathnet.ru/eng/ista/v25/i5/p55
    Translation
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Intelligent systems. Theory and applications
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024