Адрес e-mail:
Прошедшие события
Лекция о моделировании заболеваний ЦНС на рыбках данио-рерио
Панельная онлайн-дискуссия на тему «Новая волна. Акселерация будущего»
Онлайн-собрание ректората и студенческого актива института
AI 2020: технологии, рынок и управление продуктами
Родительское собрание в МФТИ
Летняя онлайн-школа «Всероссийский навигатор абитуриентов МФТИ»
Фазли Атауллаханов: «Физика свертывания крови и COVID-19»
Юрий Яровиков: «Какая математика нужна в анализе данных?»
Михаил Бурцев — об экспериментах с Memory Transformer
Даниил Поляков: «Мощь Python на все случаи жизни»
Презентация магистерской программы «Биоинформатика» ФБМФ и Napoleon IT
Александр Львовский: «Квантовая революция как мировой технологический тренд»
Выпускной МФТИ 2020: онлайн-формат не отменяет праздник
Директор ФИАН Николай Колачевский: «Наука и технологии: путь в лидерство»
Онлайн-презентация кафедры космической физики ЛФИ
Сессия вопросов-ответов с биоинформатиком Антоном Буздиным
Презентация магистерской программы «Физика сверхпроводимости и квантовых материалов»
Презентация магистерской программы «Двумерные материалы: физика и технология наноструктур»
Презентация магистерской программы «Цифровые технологии в бизнесе»
Денис Дмитриев: «Особенности поступления и ответы на вопросы. Приемная кампания — 2020»

Лекция Владимира Подольского: «Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates»

опубликовано: 20.03.2017
cached-thumb-img.3947.0.993031026196245.JPG23 марта на Межкафедральном семинаре «Теоретическая информатика и комбинаторика» в Актовом зале МФТИ в 18:30 Владимир Подольский прочтёт лекцию на английском языке «Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates». Это заседание проходит в рамках совместного семинара ФИВТ МФТИ и ФКН ВШЭ.

Abstract

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 ○ MAJk. We observe that the minimum value of k for which there exists a MAJk ○ MAJk circuit that has high correlation with the majority of n bits is equal to ϴ(n1/2). We then show that for a randomized MAJk ○ MAJkcircuit computing the majority of n input bits with high probability for every input, the minimum value of k is equal to n2=3+o(1). We show a worst case lower bound: if a MAJk ○ MAJk circuit computes the majority of n bits correctly on all inputs, then k ≥ n13=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(n2/3) can compute MAJn correctly on all inputs. 

The talk is based on joint results with Alexander Kulikov. 
Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2020 Московский физико-технический институт (национальный исследовательский университет)

Противодействие коррупции | Сведения о доходах

Политика обработки персональных данных МФТИ

Техподдержка сайта | API

Использование новостных материалов сайта возможно только при наличии активной ссылки на https://mipt.ru

МФТИ в социальных сетях