Гринберг Вадим Маркович, факультет компьютерных наук (Москва)

Номинация «Серебряный птенец»

Кандидатуру предлагают: Роман Авдеев, доцент департамент больших данных и информационного поиска факультета компьютерных наук; Дмитрий Шабанов, профессор департамента больших данных и информационного поиска факультета компьютерных наук; Михаил Вялый, профессор департамента больших данных и информационного поиска факультета компьютерных наук, ведущий научный сотрудник международная лаборатория теоретической информатики департамента больших данных и информационного поиска факультета компьютерных наук

Вадим Гринберг учится на 4 курсе бакалавриата факультета компьютерных наук НИУ ВШЭ. Это один из лучших студентов своего курса. Он не только активно учится, но и успешно работает учебным ассистентом.

Вадим последние два года проходил летнюю стажировку в лаборатории теоретической информатики в EPFL (Швейцария), где он работал с такими специалистами как М. Капралов и О. Свенссон. В работе с М. Капраловым Вадим изучал потоковые алгоритмы. Результатом работы стала модификация AGM-эскиза для графов с ограниченной степенью вершины, также при помощи методов точного разреженного восстановления (exact sparse recovery), был разработан эскиз, позволяющий точно восстановить весь граф в потоковой модели, за почти линейную память при логарифмической древесности. Для больших значений древесности был разработан двухпроходный алгоритм, решающий задачу за малую память.

На второй стажировке под руководством О. Свенссона Вадим изучал задачу покрытия звёздами (иначе называемую Minimum-load k-facility location). Были получены новые оценки целочисленного зазора (Integrality gap) для этой задачи. Относительно специфического для этой задачи критерия (возможность нарушения условия на количество фабрик - центров звёзд) получены близкие к оптимальным результаты. А именно, если разрешать открытие фабрик на 1% больше заранее заданного ограничения, удается добиться алгоритма с константной точностью приближения. Планируется публикация полученных результатов в престижном издании.

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

С Вадимом Гринбергом Шабанов Дмитрий Александрович впервые познакомился осенью 2016 года, когда в сентябре начались лекции Дмитрия Александровича по теории вероятностей на втором курсе пилотного потока ПМИ. В рамках учебного курса Вадим проявил себя блестяще, получив максимально возможные баллы. Стоит отметить его огромную мотивацию по изучению предмета, в котором он старался понять всё до мельчайших деталей. Интенсивная самостоятельная работа, изучение дополнительной литературы, знакомство заранее с ещё не пройденным материалом – всё вместе составляет идеальный образец поведения студента в учёбе.

Осенью 2017 года Шабанов Дмитрий Александрович выбрал Вадима в качестве учебного ассистента по курсу теории вероятностей для пилотного потока второго курса. Здесь Вадим также проявил себя совершенно блестяще в качестве помощника лектора, организовывая многочисленные консультации студентам, проверяя домашние задания, принимая устные коллоквиумы (в том числе и на основном потоке). Максимально сильная работа учебного ассистента. В осеннем семестре 2017/18 Вадим вошел в список лучших учебных ассистентов ФКН.

Особо хочется отметить организационную работу, которую Вадим проделывал, будучи старостой 151 группы. Фактически он был ещё одним помощником лектора, согласовывая со всем потоком даты проведения бесконечных дополнительных занятий (коллоквиумы, консультации, переписывания контрольных и др.), дедлайны по сдаче домашних заданий, обсуждая от имени студентов различные вопросы и пр. Благодаря его усилиям, в организационном плане курс прошел практически идеально. Лучшего старосту представить просто невозможно.

Успехи Вадима были неоднократно отмечены факультетом компьютерных наук. Вадим дважды (в 2017 и 2018 гг.) становился лауреатом стипендии имени Ильи Сегаловича, предназначенной для поддержки увлечённых технологиями и наукой ребят. Стипендия выдается за успехи в учёбе и научной деятельности. Также Вадим получает повышенную государственную академическую стипендию за научную и учебную деятельность на протяжении трёх семестров (осенний (4-й уровень) и весенний (2-й уровень) семестры 2017/18, осенний семестр 2018/19 (1-й уровень)).

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