Досліджено задачі комбінаторної теорії ігор і екстремальної комбінаторики. Значну увагу приділено питанням конструктивності та застосування у теорії складності обчислень і теорії дескриптивної складності. Розв'язано екстремальні задачі Рамсеївського типу для симетричних підмножин Евклідового простору, у цьому випадку значення екстремальних функцій досягаються ефективними детермінованими або ймовірнісними конструкціями. Для класу сильних ігор щодо уникнення забороненого підграфа введено та вивчено поняття симетричної стратегії. Введено поняття логічної глибини графа й одержано оцінки цього інваріанту на підставі всебічного вивчення гри Еренфойхта на графах. Ці оцінки застосовано для аналізу алгоритму Вайсфайлера - Лемана розпізнання ізоморфних графів. Шляхом ігрової інтерпретації та зведенням до екстремальних задач одержано результати про паралельне повторення інтерактивних доведень. Розроблено доведення без розголошення для теоретико-групових задач про перестановки. З'ясовано обчислювальну важкість форсингового хроматичного числа графа. Проведено оракульне конструювання, що дає змогу розв'язати питання Крайчика та Пудлака про існування оптимальних алгоритмів для coNP-задач.

• Вербіцький Олег Васильович (фізико-математичні науки)

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"