|
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.
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
Linking options:
https://www.mathnet.ru/eng/dm994https://doi.org/10.4213/dm994 https://www.mathnet.ru/eng/dm/v20/i1/p109
|
Statistics & downloads: |
Abstract page: | 411 | Full-text PDF : | 116 | References: | 30 | First page: | 5 |
|