34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). March 8–11, 2017, Hannover, Germany

Т. 66. Лейпциг : Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2017.

Под общей редакцией: H. Vollmer, B. Vallée

Главы книги

Computing majority by constant depth majority circuits with low fan-in gates

Kulikov A. S., Подольский В. В., , in: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). March 8–11, 2017, Hannover, GermanyТ. 66.: Лейпциг: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2017. P. 1–14.

We study the following computational problem: for which values of k, the majority of n bits MAJn can be computed with a depth two formula whose each gate computes a majority function of at most k bits? The corresponding computational model is denoted by MAJk o MAJk. We observe that the minimum value of k ...

Добавлено: 1 июня 2017 г.