Зимние встречи лауреатов стипендии имени Ильи Сегаловича 2017 года

В своем докладе я расскажу о проектах, в которых мне удалось поучаствовать, работая в крупнейшей виртуальной аутсорсинговой компании в мире, а так же о том, как cохранять дисциплину, находясь наедине с самим собой.

Доклад будет поделён на две части.

В первой части я расскажу про свои исследования в ходе стажировки в Theoretical Computer Science Lab в EPFL. Передо мной была поставлена задача разработки эффективных по памяти потоковых алгоритмов получения остовного леса в графов с известной древесностью (arboricity) —минимальным числом лесов, на которые можно разбить рёбра исходного графа. Существует общий метод с использованием эскизов (sketching), однако, он не даёт нижней оценки на space-complexity для данной задачи, и вполне возможно, существует лучший алгоритм, по крайней мере для широкого класса графов конкретной древесности. Будет рассказано про классический метод решения этой задачи, а также про разработанные за стажировку улучшения и альтернативные подходы, использующие свойства arboricity.

Во второй части я планирую поведать о текущей научной деятельности в качестве стажёра Международной Лаборатории Теоретической Информатики, а именно, про Sum-of-Squares-методы релаксации задач комбинаторной оптимизации. В основе метода лежит двойственность, основанная на вещественном случае Теоремы Гильберта о нулях: система полиномиальных ограничений разрешима, если и только если на пространстве полиномов существует так называемый оператор "псевдоматожидания", удовлетворяющий ограничениям системы, и связанное с ним "псевдораспределение". Мы имеем доступ только к моментам этого псевдораспределения — значениям оператора псевдоматожидания на полиномах до какой-то степени. Суть метода в том, что, если ограничения комбинаторной задачи полиномиальны, мы можем эффективно найти значения моментов нашего псевдораспределения и использовать их для получения оптимального решения. Одной из наиболее мощных техник здесь является метод перевзвешиваний распределений — получив некоторое распределение на пространстве решений, мы производим серию перевзвешиваний, сосредотачивая его в точке оптимума. Я расскажу про алгоритм максимизации полинома произвольной степени на единичной сфере, а также про поиск матрицы, близкой к одноранговой, в произвольном пространстве матриц. Будет сложно, но, надеюсь, очень интересно и познавательно!

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

В своем докладе я расскажу о том, как устроено современное представление о солнечной активности, движениях и сроке жизни солнечных пятен, а также о том, как солнечная активность связана с синхронизирующимися маятниками в Курамото-модели дифференциальных уравнений (применяемой в физхимии, биологии, медицине и анализе транспортных потоков) и случайными процессами.

В своем выступлении я расскажу про текущую научную работу в исследовательской группе байесовских методов.

В своем докладе я расскажу о совместном исследовании, в котором мы хотим выявить достаточно выразительные и вычислительно эффективные языки онтологий и запросы для доступа к данным, для которых существует переписывание в обычные запросы SQL/SPARQL над исходными данными.

Доклад будет посвящён 4-х летнему опыту работы в международной лаборатории ВШЭ. Я расскажу про плюсы и минусы совмещения работы научным сотрудником с преподаванием, про опыт взаимодействия с внешним заказчиком при решении задачи оптимизации. Также расскажу про одну из последних задач, как она решалась и в чём были сложности.

In dynamic malware analysis, programs are classified as malware or benign based on their execution logs. We propose a concept of applying monotonic classification models to the analysis process, to make the trained model’s predictions consistent over time and provably stable to the injection of any noise or ‘benign-looking’ activity into the program’s behavior. The predictions of such models change monotonically through the log, making them suitable for real-time classification on a user’s machine. We evaluate the monotonic neural network model on a large dataset of real program's execution logs and demonstrate that it provides stable and interpretable results.

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

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

Я расскажу о задаче, над которой я работал летом на стажировке в университете EPFL — о её приложениях, подходах к решению и полученных результатах.