On the complexity of monotone circuits for threshold symmetric Boolean functions

I. S. Sergeev

Diskretnaya Matematika, Tome 32 (2020) no. 1, pp. 81-109.

Résumé

The complexity of implementation of a threshold symmetric $n$-place Boolean function with threshold $k = O(1)$ via circuits over the basis $\{\vee,\, \wedge\}$ is shown not to exceed $2 \log_2 k \cdot n + o(n)$. Moreover, the complexity of a threshold-2 function is proved to be $2n+\Theta(\sqrt n)$, and the complexity of a threshold-3 function is shown to be $3n+O(\log n) $, the corresponding lower bounds are put forward.

Détail

Keywords: monotone circuits, complexity, symmetric Boolean functions, threshold functions.

Bibliographie

[1] Lupanov O. B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo MGU, M., 1984, 138 pp.

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

[3] Dunne P. E., The complexity of Boolean networks, Academic Press, San Diego, 1988, 512 pp. | MR | Zbl

[4] Knuth D. E., The art of computer programming, v. 3, Sorting and searching, Addison-Wesley, Reading, Mass., 1998 | MR

[5] Alekseev V. E., “Sorting algorithms with minimum memory”, Cybernetics, 1969, no. 5, 642–648 | DOI | Zbl

[6] Yao A. C., A study of concrete computational complexity, Ph.D. thesis. Tech. Report UIUCDCS-R-75-716, Univ. Illinois, Urbana-Champaign, 1975 | Zbl

[7] Yao A. C., “Bounds on selection networks”, SIAM J. on Computing, 9:3 (1980), 566–582 | DOI | MR | Zbl

[8] Ajtai M., Komlós J., Szemerédi E., “Sorting in $c \log n$ parallel steps”, Combinatorica, 3:1 (1983), 1–19 | DOI | MR | Zbl

[9] Pippenger N., “Selection Networks”, SIAM J. Comput., 20:5 (1991), 878–887 | DOI | MR | Zbl

[10] Jimbo S., Maruoka A., “A method of constructing selection networks with $O(\log n)$ depth”, SIAM J. Comput., 25:4 (1996), 709–739 | DOI | MR | Zbl

[11] Lamagna E. A., Savage J. E., “Combinational complexity of some monotone functions”, Proc. 15th IEEE Symp. on Switching and Automata Theory, IEEE, New Orleans, 1974, 140–144 | DOI | MR

[12] Bloniarz P. A., The complexity of monotone Boolean functions and an algorithm for finding shortest paths in a graph, Ph.D. thesis. Tech. Report No. 238, Lab. Comput. Sci., MIT, Cambridge, 1979

[13] Grinchuk M. I., “On monotone complexity of threshold functions”, Siberian Adv. Math., 44 (1994), 17–23 | MR | MR

[14] Kloss B. M., Malyshev V. A., “Otsenki slozhnosti nekotorykh klassov funktsii”, Vestnik Mosk. un-ta. Ser. 1. Matem. Mekh., 1965, no. 4, 44–51 | MR | Zbl

[15] Dunne P. E., “A $2.5n$ lower bound on the monotone network complexity of $T_3^n$”, Acta Inf., 22 (1985), 229–240 | DOI | MR | Zbl

[16] Dunne P. E., “Lower bounds on the monotone network complexity of threshold functions”, Proc. 22nd Annu. Allerton Conf. Commun., Control and Computing, Univ. Illinois, Urbana-Champaign, 1984, 911–920 | MR

[17] Bailleux O., On the expressive power of unit resolution, 2011, arXiv: 1106.3498

[18] Kučera P., Savický P., Vorel V., “A lower bound on CNF encodings of the at-most-one constraint”, Theor. Comp. Sci., 762 (2019), 51–73 | DOI | MR

[19] Mityagin B. S., Sadowskii B. N., “On linear Boolean operators”, Soviet Math. Dokl., 1965, no. 6, 1523–1527 | MR | Zbl

[20] Gashkov S. B., Kochergin V. V., “On addition chains of vectors, gate circuits, and the complexity of computations of powers”, Siberian Adv. Math., 44 (1994), 1–16 | MR

[21] Mantel W., “Problem 28”, Wiskundige Opgaven, 10 (1907), 60–61 | Zbl

[22] Jukna S., Extremal combinatorics: with applications in computer science, Springer, Berlin–Heidelberg, 2011, 414 pp. | MR | Zbl

[23] Demenkov E., Kojevnikov A., Kulikov A., Yaroslavtsev G., “New upper bounds on the Boolean circuit complexity of symmetric functions”, Inf. Proc. Letters, 110:7 (2010), 264–267 | DOI | MR | Zbl

[24] Stockmeyer L. J., “On the combinational complexity of certain symmetric Boolean functions”, Math. systems theory, 10:1 (1976), 323–336 | DOI | MR