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

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

Адрес e-mail:

Кафедральный научно-исследовательский семинар (2015 - 2016)

В весеннем семестре 2015/2016 года заседания кафедрального семинара проходят в Яндексе по вторникам в 18:30 — 20:00 в аудитории ауд. Кембридж в ШАД.

Вы можете подписаться на RSS-ленту или трансляцию в ЖЖ этого и других близких по тематике семинаров на сайте http://combalg.ru/seminars.

Предстоящие заседания:

17 мая 2016 г.
Т. Хаткевич «Алгоритмы поиска малых подграфов в случайных графах»
Анонс


Прошедшие заседания:

19 апреля 2016 г. 
А.В. Куликов «Хеджирование ценового риска на товарных рынках в присутствии валютного и объемного рисков» 
Анонс


12 апреля 2016 г. 
А.П. Купцов, Э.Ю. Лернер «Потоковые многочлены как фейнмановские амплитуды и альфа-представление для них» 
Хроматические и потоковые многочлены можно рассматривать как фейнмановские амплитуды (в координатном и соответственно импульсном пространстве) над кольцом вычетов по модулю. 
Техника так называемого \alpha-представления, применяемая в теории фейнмановских амплитуд, позволяет (в случае когда число вычетов — нечётное простое или его степень) записать потоковый многочлен в виде суммы символов Лежандра от суммы по произведениям переменных, соответствующих деревьям исходного графа. Авторы надеются что это новое представление поможет подобраться к интригующим нерешённым проблемам для потокого многочлена.


5 апреля 2016 г. 
М. Попов «Сравнительный анализ методов оценивания бикликового покрытия» 
В данном докладе я сравню различные методы доказательства нижних оценок для размера бикликового покрытия графов и расскажу о применении этих оценок в теории коммуникационной сложности. Главным образом сравнивается классический метод трудных множеств (fooling sets в англоязычной литературе) и более новых методов Юкны и Куликова и метода энтропийных неравенств. Также будет рассказано про обобщения этих оценок на случай n-мерного коммуникационного протокола.


29 марта 2016 г. 
I. Mabillard «A higher-multiplicity whitney trick and counterexamples to the topological tverberg conjecture» 
Let’s assume that r balls intersect in R^d in general position and that their intersection consists of two points of opposite intersection signs. I’ll describe a generalization of the classical Whitney Trick to this situation: our goal is to eliminate the pair of intersection points, by means of ambient isotopies having "small" support. A neat application and our original motivation to prove this "generalized Whitney trick" is the construction of counterexamples to the Topological Tverberg Conjecture, which asserts that for any continuous map from the N-simplex to R^d, one can always find "a large number" of disjoint cells of the N-simplex that intersect in the image in R^d. 
Our Whitney trick requires a technical "codimension assumption" to work, so in order to use it and obtain counterexamples to the topological Tverberg, one needs to overcome this dimensional barrier. Two methods have been found so far: the first, due to Frick, uses a combinatorial trick found by Gromov (and rediscovered by Blagojevic-Frick-Ziegler), yielding counterexamples in dimension d>18. The second method uses a restricted class of "prismatic maps" and yields counterexamples in dimension d>11. 
What happens in lower dimensions remains a mystery… 
(Joint work with S. Avvakumov, A. Skopenkov, and U. Wagner)


22 марта 2016 г. (заседание на ФКН ВШЭ, Кочновский проезд, д. 3, м. Аэропорт) 
M. Vizer «Finding a majority ball with majority answers» 
Suppose we are given a set of n balls {b_1,... ,b_n} each colored either red or blue in some way unknown to us. We can query any triple of balls {b_{i_1},b_{i_2},b_{i_3}}. 
As an answer to such a query we obtain (the index of) a majority ball, that is, a ball whose color is the same as the color of another ball from the triple. 
Our goal is to find a non-minority ball, that is, a ball whose color occurs at least n/2 times among the n balls. We show that the minimum number of queries needed to solve this problem is Theta(n) in the adaptive case and Theta(n^3) in the non-adaptive case. We also consider some related problems. 
Joint work with D. Gerbner, B. Keszegh, D. Palvolgyi, B. Patkos and G Wiener


1 марта 2016 г. 
Pim van der Hoorn «Distances in the configuration model» 
An interesting feature of many real world networks is that they have short paths, meaning that the average distance scales as the logarithm of the size of the graph. This phenomenon is usually referred to as the small world property. In this talk I will discuss how distances behave in the well-studied configuration model. I will start with result for the undirected case, mostly due to work by van den Esker, van der Hofstad, Hooghiemstra and Van Mieghem. I will show how the behavior of the shortest path between two randomly sampled nodes changes with the existence of moments of the degree distribution. Then I will move to more recent work on distances in the directed configuration model, which is based on joint work with Mariana Olvera-Cravioto. I will show that here distances behave similarly to the undirected case but that it is the joint distribution of the in- and out-degree of a vertex that plays an important role. I will end with some result on universality of distances in graphs and some interesting open questions.

9 февраля 2016 г.
М. Славошевский «Метод стохастического градиентного спуска: сходимость и асимптотические свойства для сильно выпуклых функций»
На докладе будет обсуждаться метод стохастического градиентного спуска (SGD) - вероятностный алгоритм оптимизации функций, используемый в машинном обучении.
Основное внимание будет уделено случаю применения этого метода по отношению к так называемым сильно выпуклым функциям при оптимизации на выпуклом замкнутом множестве банахова пространства: асимптотические доверительные интервалы и асимптотическая ковариационная матрица.
Доклад в существенной степени будет опираться на сведения из следующих областей:

01 декабря 2015 г.
Е.А. Авксентьев «Инвариантные меры и теоремы о замыкании Понселе»
Анонс

24 ноября 2015 г. (Внимание! Семинар пройдет в комн. 307 ИППИ РАН, Большой Каретный пер., 19)
М.Е. Жуковский «Свойства первого порядка случайного графа Эрдеша-Реньи»
Говорят, что случайный граф Эрдеша-Реньи подчиняется k-закону нуля или единицы, если для любого свойства, записанного с помощью формулы первого порядка, кванторная глубина которой не превосходит числа k, вероятность им обладать стремится либо к нулю, либо к единице. В 1988 году Дж. Спенсер и С. Шела доказали, что случайный граф Эрдеша-Реньи подчиняется k-закону нуля или единицы, если вероятность ребра является степенной функцией от количества вершин графа, где показатель степени – отрицательное иррациональное число. Мы нашли различные диапазоны рациональных значений показателя степени в вероятности ребра случайного графа, при которых он подчиняется k-закону нуля или единицы. Эффект отсутствия закона нуля или единицы, в частности, вызван тем, что для некоторых простых свойств первого порядка (например, экзистенциальных) существует пороговая вероятность, которая как раз равна степени числа вершин с соответствующим рациональным показателем. Под пороговой вероятностью свойства подразумевается такая функция от числа вершин, что при вероятности проведения ребра, асимптотически меньшей этой функции, вероятность выполнения свойства стремится к нулю, а при большей – к единице (или наоборот).  Разумеется, пороговых вероятностей может быть более одной для одного свойства. Множество рациональных показателей степени в вероятностях проведения ребра, которые являются пороговыми вероятностями, называется спектром рассматриваемого свойства. В 1990 году Дж. Спенсер доказал, что существуют свойства первого порядка с бесконечным спектром. Спектром числа k мы называем объединение спектров всех свойств, выразимых формулами первого порядка, кванторные глубины которых не превосходятk. Дж. Спенсер доказал, что при достаточно больших k число 1/3 является предельной точкой в спектре числа k. Мы оценили минимальный и максимальный элементы спектров, а также минимальное значение k, при котором спектр бесконечен.

10 ноября 2015 г.
А.Б. Скопенков «Контрпримеры к топологической гипотезе Тверберга»

13 октября 2015 г.
А.В. Крот «Local clustering coefficient in preferential attachment graphs»
В докладе описывается новый алгоритм генерации случайных графов, основанный на методе отсева активных пользователей. Получаемые графы обладают статистическими характеристиками, схожими с реальными социальными сетями: степенным распределением степеней вершин, малым средним кратчайшим путём, положительной ассортативностью, высокой степенью кластеризации, низкой плотностью. Алгоритм моделирует процессы образования реальных социальных сетей, структурно прост и характеризуется малым количеством параметров.

6 октября 2015 г.
Ф.С. Стонякин «Аналоги задачи о справедливом разделе ресурсов»
Хорошо известны задачи о справедливом разделе сокровищ (ресурсов), связанные с теорией меры. В классических задачах такого типа делимый объект обозначают как множество A, а части – как некоторую систему подмножеств. Предполагается, что каждый субъект оценивает части А с помощью некоторой безатомной меры. Разрешимость такого рода задач, как правило, в той или иной степени связана с теоремой Ляпунова о выпуклости образа безатомных векторных мер.
Однако такие подходы неудобны в некоторых ситуациях. Например, если рассмотреть ситуацию пренебрежения малыми величинами. В таком случае можно выделить класс достаточно малых подмножеств и приписать им нулевую оценку. Но объединение нескольких малых множеств может быть уже не малым и иметь ненулевую оценку. Иными словами, функция оценки множеств может быть неаддитивной и терять свойство безатомности.
В этой связи мы вводим неаддитивные аналоги понятия меры множества, которые моделируют описанную выше ситуацию. Исследованы свойства этих аналогов мер, получен аналог теоремы Ляпунова о выпуклости в специальной форме. На базе этих понятий рассмотрены соответствующие задачи о разделе ресурсов и доказаны результаты об их разрешимости. Обсуждаются бесконечномерные аналоги задачи о разделе ресурсов, моделирующие сближение бесконечного числа критериев на специальных разбиениях исходного множества.

29 сентября 2015 г.
А.В. Кудинов «Об одной старой просто формулируемой нерешенной проблеме в модальной логике»
Я расскажу об одной старой проблеме в модальной логике, которая до сих пор не поддается усилиям ученых.
Формулируется она так: разрешима ли логика, задаваемая формулой \Box \Box p -> \Box \Box \Box p.
В общем случае это n боксов p влечет m боксов p.
Также я расскажу некоторые продвижения в решении этой задачи, которые были сделаны докладчиком в совместной работе с И.Шапировским. Мы доказали, разрешимость этих логик с некоторыми дополнительными естественными аксиомами.
Задачу можно переформулировать в терминах направленных графов. И, судя по всему, в решении этой задачи могут помочь какие-то методы разработанные в теории графов. Поэтому я надеюсь, что слушателям будет интересно узнать о связи логики с теорией графов и, возможно, появятся идеи, которые могут помочь в дальнейшей атаке на эту проблему.

22 сентября 2015 г.
А. Горский «Спонтанное нарушение симметрии и критические явления в двухцветных сетях»
Исследование статистических свойств графов с разноцветными вершинами в последнее время становится новым популярным сюжетом теории случайных сетей. Модели, использующие представление о "цветных" графах описывают исключительно широкий класс физических систем: от оптимизации распределенных сообществ типа "производитель-потребитель" до изменения топологии  (baby universes) в космологии и теории струн.
Мы изучаем равновесные свойства эволюционирующих случайных сетей, имеющих два типа вершин, белые и черные. Эволюция сети заключается в таком переключении связей, которое ведет к увеличению числа одноцветных троек связанных вершин. При этом число связей, выходящих из каждой вершины, сохраняется.
Мы обнаружили, что при увеличении (от нуля) энергии одноцветных троек связанных вершин, сеть разбивается на одноцветные кластеры (черный и белый), которые оказываются связаны между собой пучком ("струной") черно-белых связей. Неожиданное явление заключается в том, что данная струна остается стабильной (число связей в пучке не меняется) в широком интервале энергий одноцветных троек.
Мы обсуждаем данный эффект с точки зрения перехода газ-жидкость в классической термодинамике, а так же с точки зрения двумерной гравитации. Высказывается гипотеза, что наличие широкого плато в зависимости числа черно-белых связей между кластерами от энергии одноцветных троек - есть проявление свойства "квантовой запутанности" в классической системе и должно быть принято во внимание при анализе свойств реальных сетей. связывающих, например, производителей с потребителями.

Заседания 2014-2015 учебного года
Заседания 2013-2014 учебного года
Заседания 2012-2013 учебного года

Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

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

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

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

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