• 23 марта 2017, четверг
  • Москва, Институтский переулок, 9с2, МФТИ, Лабораторный Корпус, Актовый Зал

В.В. Подольский - Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates

Регистрация на событие закрыта

Извините, регистрация закрыта. Возможно, на событие уже зарегистрировалось слишком много человек, либо истек срок регистрации. Подробности Вы можете узнать у организаторов события.

Другие события организатора

Школа Прикладной Математики и Информатики МФТИ
2562 дня назад
23 марта 2017, начало в 18:30
Москва
Институтский переулок, 9с2, МФТИ, Лабораторный Корпус, Актовый Зал

Межкафедральный семинар в МФТИ по дискретной математике

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 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 \ge 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 (arxiv.org/pdf/1610.02686.pdf...)

Страница семинара: www.mathnet.ru/php/conference.phtml...

 

Регистрация

Рекомендуемые события

Организуете события? Обратите внимание на TimePad!

Профессиональная билетная система, статистика продаж 24/7, выгрузка списков участников, встроенные инструменты продвижения, личный кабинет для самостоятельного управления и еще много чего интересного.

Узнать больше