JetBrains Research — наука, меняющая мир

Слегка субкубический алгоритм для задачи поиска путей с контекстно-свободными ограничениями

Все мы так или иначе сталкиваемся с задачами, решаемыми за полиномиальное время. Но есть такие задачи, для которых кубическое или, например, квадратичное время работы является слишком неэффективным для использования на практике. Возникает вопрос, может ли конкретная задача быть решена немного быстрее, например, хотя бы за субкубическое (n^{3-e}) (или субквадратичное) время? Если нет, то как показать, что такое время работы оптимально?

В докладе будет рассмотрена одна из таких задач -- задача поиска путей с контекстно-свободными ограничениями (CFL-reachability), к которой сводится большое количество задач анализа программ. Вопрос о существовании субкубического алгоритма для решения этой задачи является открытым уже более 30 лет. Оптимально ли классическое кубическое решение? Мы попробуем ответить на этот вопрос, используя инструменты современного направления теории сложности -- fine-grained complexity. Также будет показано, как ускорить время решения на логарифмический фактор, получив тем самым ""слегка субкубический"" алгоритм для задачи CFL-reachability.

Докладчик: Екатерина Шеметова

Материалы:

1) Orachev E., Epelbaum I., Azimov R., Grigorev S. (2020). Context-Free Path Querying by Kronecker Product. In: Darmont J., Novikov B., Wrembel R. (eds) Advances in Databases and Information Systems. ADBIS 2020. Lecture Notes in Computer Science, vol 12245. Springer, Cham.

2) Williams, V. (2019). ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY.

3) Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. (2015). Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (STOC '15).

Семинар пройдет онлайн 28 сентября в 17:30, ссылка Google meet: https://meet.google.com/myu-dhmz-gvu