Выпускники рассказывают: Вадим Гринберг

Вадим дважды получил стипендию имени Ильи Сегаловича в 2017 и 2018 году, а также на четвертом курсе стал лауреатом премии “Золотая Вышка” в номинации “Серебряный птенец”. Дважды стажировался в EPFL (Федеральная политехническая школа Лозанны) в 2017 и 2018 годах, работал в международной лаборатории теоретической информатики. В этом году Вадим окончил бакалаврскую программу ФКН “Прикладная математика и информатика” с красным дипломом. Сейчас выпускник факультета проходит летнюю стажировку в Weizmann Institute of Science в Израиле, а затем уедет на PhD в Toyota Technological Institute at Chicago в Чикаго, США.


Почему ты решил поступить в Вышку на ПМИ?
Решение по большей части основывалось на интуиции и внутреннем чутье. Мне казалось, что здесь будет классно, и я смогу добиться своих целей, какими бы они ни были. На момент поступления я твёрдо понимал, что хочу заниматься чем-то, связанным с математикой, однако, абитуриент плохо представляет себе весь спектр возможных родов деятельности, не говоря уже о путях к успеху в тех или иных сферах. Вышка в то время набирала обороты в математической сфере, и я подумывал податься либо на ПМИ, либо на Матфак. Быть чистым математиком, мне не хотелось, уж больно абстрактно и запутанно. При этом компьютерные науки завоевывали мир, так или иначе проявляя себя в различных областях. Вот и пошёл сюда, пусть даже вообще не умел программировать и слабо представлял, кем стану после выпуска.

Чем ты занимался на летней стажировке в EPFL (Федеральная политехническая школа Лозанны)?
В EPFL я был дважды — летом 2017 года и летом 2018. 

Во время своей первой поездки я вместе с Данилой Кутениным занимался потоковыми алгоритмами на графах, под руководством Михаила Капралова. Мы занимались задачей связности динамического потокового графа. Дан граф в потоке, необходимо разработать алгоритм, с большой вероятностью за один проход по потоку восстанавливающий остовный лес графа. В 2012 году был придуман первый алгоритм решения. Наша цель заключалась в разработке его улучшения — более эффективного по памяти алгоритма, для класса графов ограниченной древесности. 

На второй стажировке я занимался приближенными алгоритмами для задач комбинаторной оптимизации, под руководством Олы Свенссона. Одной из тем исследований была задача о минимальном k-звёздном покрытии. Нам дано конечное метрическое пространство и множества фабрик и клиентов. Необходимо открыть не более k фабрик и таким образом распределить клиентов по фабрикам, чтобы максимальный вес каждой фабрики (сумма расстояний до обслуживаемых клиентов) был как можно меньше. В целом задача напоминает известную k-Facility Location, отличие заключается в том, что вместо минимизации суммы расстояний от фабрик до обслуживаемых клиентов мы минимизируем максимальную частичную сумму этих расстояний для каждой из открытых фабрик. Естественным образом, задача NP-полная, неизвестно даже хороших приближённых алгоритмов. Вместе с профессором Свенссоном мы смогли разработать первый в мире полиномиальный алгоритм, получающий двустороннее константное приближение для этой задачи – открыв (1 + eps) k фабрик мы получаем решение, хуже оптимального не более чем в O (1/eps^2) раз. Также мы получили первый аналогичный результат для зеркальной задачи, где надо минимизировать количество открытых фабрик при условии ограничений на максимальную сумму расстояний, кроме того, мы смогли получить некоторые нижние оценки на возможную точность приближения. Алгоритмы существенно основаны на техниках линейного программирования, и мне очень пригодились знания и навыки, что я получил на курсах Дискретной Математики 2 на ПМИ и Комбинаторной Оптимизации в ШАДе. В данный момент мы всё ещё продолжаем сотрудничество с Олой, улучшая полученные результаты и готовя их к публикации.

Расскажи про свои исследования в международной лаборатории теоретической информатики
Вместе с Михаилом Николаевичем Вялым я занимался изучением приближённых алгоритмов для NP-трудных задач. Основным предметом исследований был так называемый метод сумм квадратов — один из наиболее популярных методов выпуклой релаксации задач комбинаторной оптимизации, используемый для построения аппроксимационных алгоритмов и изучения трудности приближений. С помощью этого метода были получены лучшие приближённые алгоритмы для многих NP-трудных задач, а также доказано множество нижних оценок. 

В своей дипломной работе я занимался изучением подхода к округлению релаксаций сумм квадратов, основанном на близости решений релаксации к гомоморфизмам алгебры функций на булевом кубе. Тема, мягко говоря, непростая, но довольно интересная. Позволяет посмотреть на метод сумм квадратов с принципиально новой стороны. Мы также рассмотрели возможные приложения этого подхода к улучшению существующей точности аппроксимации для задачи о максимальном разрезе, получив некоторые интригующие результаты.

Что было самое запоминающееся во время учёбы?
Самой запоминающейся я бы назвал серию событий, озаглавленную как "Шабанов Дмитрий Александрович". Я получил огромное удовольствие от Теории Вероятностей и Математической Статистики, что читал Дмитрий Александрович на пилотном потоке второго курса обучения. Идеальное сочетание сложности, вызова и захватывающей интересности как рассказываемого материала, так и предлагаемых к решению задач. Ну и конечно же, мастерства ведения лекций. Всё это и вдохновило меня записаться на факультатив дополнительных глав ТеорВера и пойти ассистентом по ТВиМСу на пилотный поток на следующие два года. 

Курсы, которые читает Дмитрий Александрович, обладают удивительным свойством заманивать и притягивать. Именно поэтому мы с группой "поклонников Шабанова" пошли сначала на факультатив ДопГлав МатСтата на третьем курсе, а также на годовой магистрский курс по Случайным Графам, который Дмитрий Александрович читает на Физтехе, от которых получили фантастический кайф и солидную гору знаний. В своих исследованиях, как ранее, так и сейчас, мне регулярно приходится иметь дела с вероятностью и случайными графами, во всевозможных вариациях и проявлениях, и пройденные курсы позволяют уверенно себя чувствовать на научном поле боя. Я очень благодарен Дмитрию Александровичу за все проведенные вместе годы.

Чем ты сейчас занимаешься?
В данный момент я нахожусь на стажировке в Weizmann Institute of Science в Израиле. 

Попал я сюда спонтанно. В апреле я раздумывал о том, а что делать летом в промежуток после выпуска и до отъезда в Америку на PhD. Сидеть без дела было бы неприемлемо, поэтому я перебирал различные варианты исследовательских стажировок. И вот однажды ночью я просыпаюсь с мыслью, что мне обязательно нужно поехать в Израиль на лето. В ходе своих исследований в комбинаторной оптимизации я часто сталкивался с работами профессора Уриэля Фейге из Вейцмана, решил написать ему, кто я такой, чем занимаюсь и что буду рад поработать с ним летом. Написал и лёг спать. Наутро просыпаюсь и вижу ответ от Фейге: "Хорошо, давай поработаем". Так и попал на стажировку.

Здесь я занимаюсь алгоритмами на случайных графах, расскажу подробнее о теме работы. Есть известная задача о скрытой клике — берется случайный граф и случайные k вершин в нем, затем на этих k вершинах строится клика (допроводятся недостающие рёбра). Необходимо за полиномиальное время отыскать какую-то клику размера хотя бы k в полученном вышеуказанным образом графе. Есть множество алгоритмов, которые умеют это делать для разных значений k. Моя задача несколько иная — клика размера k делается не случайно, вместо этого “противник” выбирает произвольные k вершин в уже сформированном случайном графе, на свое усмотрение (например, он может выбрать k вершин наименьшей/наибольшей степени, или ещё какой плохой случай). Нужно понять, для каких значений k в такой полу случайной постановке задачи существует полиномиальный алгоритм поиска клики размера хотя бы k, вне зависимости от выбора противника. Пару лет назад Фейге уже ответил на аналогичный вопрос для задачи о скрытом k-раскрашивании, и теперь хочет разобраться, что происходит для клик. 

Расскажи о том, как ты поступал на PhD и как выбирал университет?
Я поступил на PhD в Toyota Technological Institute at Chicago, что находится, собственно, в Чикаго. Институт является одним из ведущих в теоретической информатике, особенно в областях комбинаторной оптимизации и приближенных алгоритмов — чем я и занимаюсь. 

Об институте я впервые услышал осенью 2017 года, когда в Вышку с визитом приехали Константин и Юрий Макарычевы, известные специалисты в теоретической информатике. Они рассказывали ребятам с нашей специализации (Теоретическая информатика) о возможностях поступления в аспирантуру в Америке и о ведущих американских вузах в теоринфе. Собственно, Юрий является профессором TTIC, и занимается преимущественно аппроксимационными алгоритмами для задач комбинаторной оптимизации. По отзывам моих знакомых учёных (и самого Юрия, естественно), TTIC является хорошим местом для рисёрча в приближённых алгоритмах.

Подавался я в двенадцать вузов, среди которых были как и широко известные (MIT, Stanford, CMU, GaTech, EPFL), так и менее известные (тот же TTIC, например). Оценки у меня были отличные, языковые экзамены сдал высоко, опыт исследований в теоретической информатике был хороший (и хорошие рекомендации), поэтому, как я рассчитывал, у меня были неплохие шансы попасть в лучшие вузы. По итогу меня приняли в шесть из них (среди которых были TTIC, EPFL и GaTech). Надо было выбирать, где делать PhD. 

Несмотря на то, что с учёными из EPFL мы уже неплохо сработались и знали друг друга, мне всё же хотелось в американский вуз — больше возможностей и потенциальных знакомств и коллабораций, а также более широкий спектр изучаемых вопросов. Выбор пал на TTIC по следующим причинам. Во-первых, здесь очень сильная команда в сфере аппроксимационных алгоритмов и комбинаторной оптимизации. Во-вторых, во время своей стажировки в EPFL я столкнулся с несколькими работами Юлии Чужой, профессора TTIC, которая занимается разнообразными задачами в том числе в приближённых алгоритмах. Мне понравился стиль и, как бы выразиться, "мощность и фундаментальность" её работ. Мы несколько раз пообщались по Скайпу о науке и об обучении, и я решил, что было бы весьма круто поучиться и поработать с Юлией. Наконец, TTIC находится в Чикаго, одном из крупнейших индустриальных центров Америки, а мне весьма нравятся крупные города. Кроме того, в штате Иллинойс, неподалёку от Чикаго, находится целый кластер университетов с сильными теоретическими группами (UIUC, UChicago, Northwestern), и всегда будет возможность туда съездить с целью рисёрча.

Какие у тебя ожидания от учебы в TTIC? 
Буду честен: ожидаю, что её будет мало, чтобы я мог посвятить всё имеющееся время исследованиям. Во время обучения на ПМИ я брал множество факультативов и сложных магистерских курсов в ШАДе и Физтехе как раз с той целью, чтобы как можно больше знать и уметь на момент окончания бакалавриата — тогда обучение в аспирантуре пойдет в разы легче. Плюс ТеорИнфы на ПМИ в том, что многие наши бакалаврские курсы являются весьма advanced по меркам зарубежных вузов, и проходятся только в магистратуре/аспирантуре. Что дает огромную фору выпускникам специализации ТИ, с полной самоотдачей учившимся весь бакалавриат, и позволяет больше времени уделять рисёрчу в будущем.