|
Intelligent systems. Theory and applications, 2021, Volume 25, Issue 2, Pages 131–154
(Mi ista307)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
Part 3. Mathematical models
The complexity of multilayer $d$-dimensional circuits
T. Sitdikova, G. V. Kalachevb a Google LLC
b Lomonosov Moscow State University
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 \left(\frac{2^n}{n}, \frac{2^n (1 - \lambda)}{\log k} \right)$ 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.
Citation:
T. Sitdikov, G. V. Kalachev, “The complexity of multilayer $d$-dimensional circuits”, Intelligent systems. Theory and applications, 25:2 (2021), 131–154
Linking options:
https://www.mathnet.ru/eng/ista307 https://www.mathnet.ru/eng/ista/v25/i2/p131
|
|