Современные базы данных и аналитические системы используют индексные структуры для ускорения поиска информации. Интерес представляют индексы, адаптирующиеся к распределению данных или запросов, но их применение требует периодического полного перестроения. Я разработал алгоритмы построения структур SplayList и RadixSpline, эффективные для многоядерных систем.

Эти алгоритмы обеспечивают ускорение построения до 17−28 раз по сравнению с последовательными реализациями на сервере с 48 потоками. Для RadixSpline я также предложил новый алгоритм, который параллельно строит более компактный индекс. Результаты работы могут использоваться в системах хранения и обработки больших данных.

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

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

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

Построенные с помощью моего алгоритма коды имеют высокое минимальное расстояние и улучшенный весовой спектр, а по корректирующей способности близки или превосходят коды, полученные другими методами. Сейчас полярные коды используются в стандарте 5G и ожидается, что в будущем их применение будет расширено.

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

Я разработал параметризованный алгоритм, который проверяет, можно ли улучшить эту оценку на заданном графе. Работа содержит интересные структурных идеи и представляет большой теоретический интерес. Совсем скоро я выступлю с ней на ESA — Европейском симпозиуме по алгоритмам.

Суть моей работы — ускорение верификации многопоточных программ, использующих различные конкурентные структуры данных в GenMC. Само ускорение достигается за счет подмены имплементаций конкурентных структур данных на более простые спецификации.

В рамках данной работы я расширил модель памяти RC11 до модели памяти dRC11. Также я заметил некоторые прежде неизвестные проблемы в теории, стоящей за abstraction theorem в dRC11 и сформулировал новую, более понятную и корректно работающую версию abstraction theorem. Она позволяет определить, можно ли использовать одну структуру данных вместо другой без потери каких-либо поведений клиента, тем самым отвечая на вопрос, можно ли использовать спецификацию вместо имлементации в любой программе.

Что такое Generic Model Checker