Одним из главных принципов уникальной «системы Физтеха», заложенной в основу образования в МФТИ, является тщательный отбор одаренных и склонных к творческой работе представителей молодежи. Абитуриентами Физтеха становятся самые талантливые и высокообразованные выпускники школ всей России и десятков стран мира.

Студенческая жизнь в МФТИ насыщенна и разнообразна. Студенты активно совмещают учебную деятельность с занятиями спортом, участием в культурно-массовых мероприятиях, а также их организации. Администрация института всячески поддерживает инициативу и заботится о благополучии студентов. Так, ведется непрерывная работа по расширению студенческого городка и улучшению быта студентов.

Адрес e-mail:

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

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 ○ MAJk circuit 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 kn13=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.

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

soc-vk soc-fb soc-tw soc-li soc-li soc-yt
Яндекс.Метрика