  RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  Ближайшие семинары Календарь семинаров Список семинаров Архив по годам Регистрация семинара Поиск RSS Ближайшие семинары

Межкафедральный семинар МФТИ по дискретной математике
23 марта 2017 г. 18:30, г. Долгопрудный, Актовый зал Лабораторного корпуса МФТИ  Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates

В. В. Подольский

 Количество просмотров: Эта страница: 88

Аннотация: We study the following computational problem: for which values of \$k\$, the majority of \$n\$ bits \$MAJ_n\$ 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 \$MAJ_k \circ MAJ_k\$. We observe that the minimum value of \$k\$ for which there exists a \$MAJ_k \circ MAJ_k\$ circuit that has high correlation with the majority of \$n\$ bits is equal to \$\Theta(n^{1/2})\$. We then show that for a randomized \$MAJ_k \circ MAJ_k\$ circuit computing the majority of \$n\$ input bits with high probability for every input, the minimum value of \$k\$ is equal to \$n^{2/3+o(1)}\$. We show a worst case lower bound: if a \$MAJ_k \circ MAJ_k\$ circuit computes the majority of \$n\$ bits correctly on all inputs, then \$k\geq n^{13/19+o(1)}\$. This lower bound exceeds the optimal value for randomized circuits and thus is unreachable for pure randomized techniques. For depth \$3\$ circuits we show that a circuit with \$k= O(n^{2/3})\$ can compute \$MAJ_n\$ correctly on all inputs.
The talk is based on joint results with Alexander Kulikov.

 ОТПРАВИТЬ:       Обратная связь: math-net2020_01 [at] mi-ras ru Пользовательское соглашение Регистрация Логотипы © Математический институт им. В. А. Стеклова РАН, 2020