On the complexity of linear Boolean operators with thin matrixes

S. B. Gashkov ; I. S. Sergeev

Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 3, pp. 3-18.

Résumé

It is considered the problem of construction of a “rectangle-free” Boolean $(n\times n)$-matrix $A$ (i.e. a matrix without ($2\times2$)-submatrixes of all unities) such that the corresponding linear mapping modulo 2 has complexity $o(\nu(A)-n)$ in the basis $\{\oplus\}$, where $\nu(A)$ is the weight of $A$, i.e. the number of unities. (In the paper by Mityagin and Sadovskiy (1965), where the problem was originally studied, “rectangle-free” matrixes were called thin matrixes.) Two constructions for solving the problem are introduced. In the first example $n=p^2$, where $p$ is an odd prime number. The weight of the corresponding matrix $H_p$ is $p^3$ and the complexity of the corresponding linear operator is $O(p^2\log p\log\log p)$. The matrix in the second example has weight $nk$, where $k$ is the cardinality of the Sidon set in $\mathbb Z_n$. One can put $k=\Theta(\sqrt n)$; for some $n$, Sidon sets of cardinality $k\sim\sqrt n$ are known. The complexity of the corresponding linear mapping is $O(n\log n\log\log n)$. Some generalizations of the problem are also considered. Bibl. 29.

Détail

Keywords: Boolean circuit, complexity, linear Boolean operator, finite field
Mots-clés : discrete Fourier transform, circulant matrix, Sidon set.

Bibliographie

[1] Andreev E., “Ob odnom semeistve bulevykh matrits”, Vestn. MGU. Matematika. Mekhanika, 1986, no. 2, 97–100 | Zbl

[2] Ansel Zh., “Minimalnoe chislo zamykayuschikh kontaktov, dostatochnoe dlya realizatsii simmetricheskoi bulevoi funktsii $n$ peremennykh”, Kiberneticheskii sb., 5, Mir, M., 1968, 47–52

[3] Bleikhut R., Bystrye algoritmy tsifrovoi obrabotki signalov, Mir, M., 1989, 448 pp. | MR

[4] Braun U. G., “Grafy, ne soderzhaschie grafa Tomsena”, Kiberneticheskii sb., 18, Mir, M., 1981, 34–38

[5] Grinchuk M. I., “O slozhnosti realizatsii posledovatelnosti bulevykh matrits ventilnymi skhemami razlichnoi glubiny”, Metody diskretnogo analiza v sinteze upravlyayuschikh sistem, 44, 1986, 3–23 | MR | Zbl

[6] Grinchuk M. I., “O slozhnosti realizatsii tsiklicheskikh bulevykh matrits ventilnymi skhemami”, Izv. vuzov. Matematika, 1988, no. 7, 39–44 | MR | Zbl

[7] Zykov K. A., “O sravnenii slozhnosti dvukh sposobov realizatsii nekotorykh lineinykh bulevykh preobrazovanii”, Diskret. matematika, 8:2 (1996), 151–159 | MR | Zbl

[8] Zykov K. A., “O slozhnosti realizatsii lineinykh bulevykh preobrazovanii skhemami glubiny tri”, Vest. MGU. Matematika. Mekhanika, 1998, no. 2, 68–70 | MR | Zbl

[9] Kartesi F., Vvedenie v konechnye geometrii, Mir, M., 1980, 320 pp. | MR

[10] Krichevskii R. E., “O slozhnosti parallelno-posledovatelnykh skhem, realizuyuschikh odnu posledovatelnost bulevykh funktsii”, Problemy kibernetiki, 12, Nauka, M., 1964, 45–55

[11] Lupanov O. B., “O ventilnykh i kontaktno-ventilnykh skhemakh”, Dokl. AN SSSR, 111:6 (1956), 1171–1174 | MR | Zbl

[12] Melkhorn K., “Nekotorye zamechaniya, kasayuschiesya bulevykh summ”, Kiberneticheskii sb, 18, Mir, M., 1981, 39–45

[13] Mityagin B. S., Sadovskii B. N., “O lineinykh bulevskikh operatorakh”, Dokl. AN SSSR, 165:4 (1965), 773–776 | Zbl

[14] Nechiporuk E. I., “Referat 1.V.206”, RZhMat., 1967, no. 1

[15] Nechiporuk E. I., “Ob odnoi bulevskoi matritse”, Problemy kibernetiki, 21, Nauka, M., 1969, 237–240 | MR

[16] Toom A. L., “O slozhnosti skhemy iz funktsionalnykh elementov, realizuyuschei umnozhenie tselykh chisel”, Dokl. AN SSSR, 150:3 (1963), 496–498 | MR | Zbl

[17] Kholl M., Kombinatorika, Mir, M., 1970, 424 pp. | MR

[18] Erdësh P., Spenser Dzh., Veroyatnostnye metody v kombinatorike, Mir, M., 1976, 130 pp. | MR

[19] Alon N., Karchmer M., Wigderson A., “Linear circuits over $\mathrm{GF}(2)$”, SIAM J. Comput., 19:6 (1990), 1064–1067 | DOI | MR | Zbl

[20] Bernstein D. J., The transposition principle http://cr.yp.to/transposition.html

[21] Bini D., Pan V., Polynomial and matrix computations, v. 1, Birkhäuser, Boston, 1994, 415 pp. | MR | Zbl

[22] Cantor D., Kaltofen E., “On fast multiplication of polynomials over arbitrary algebras”, Acta Inf., 28:7 (1991), 693–701 | DOI | MR | Zbl

[23] Chandra A. K., Fortune S., Lipton R., “Unbounded fan-in circuits and associative functions”, Proc. $15$th ACM Symp. Theory Comput., ACM, New-York, 1983, 52–60

[24] Kóllar J., Rónyai L., Szabó T., “Norm-graphs and bipartite Turán numbers”, Combinatorica, 16:3 (1996), 399–406 | DOI | MR | Zbl

[25] Kövari T., Sós V. T., Turán P., “On a problem of K. Zarankiewicz”, Coll. Math., 3 (1954), 50–57 | MR | Zbl

[26] Lamagna E. A., Savage J. E., “Computational complexity of some monotone functions”, Proc. $15$th SWAT Conference, IEEE Comput. Soc. Press, Long Beach, 1974, 140–144 | MR

[27] O'Bryant K., “A complete annotated bibliography of work related to Sidon sequences”, Elect. J. Comb., 11, Dynamic survey (2004), 39 pp.

[28] Schönhage A., “Schnelle multiplikation von polynomen über körpern der charakteristik 2”, Acta Inf., 7 (1977), 395–398 | DOI | MR | Zbl

[29] Wegener I., The complexity of Boolean functions, Wiley, Stuttgart, 1987, 470 pp. | MR | Zbl