Сложность вычислений 12. Вероятностная сложность (продолжение). Простейшие техники дерандомизации

Привет, таймкоды сложностей: 00:00:00 - заставка 00:02:19 - амплификация RP 00:08:52 - амплификация BPP 00:17:40 - теорема Эйдлмана 00:24:14 - теорема Гача-Сипсера-Лаутемана 00:43:28 - дерандомизация MAXCUT 00:55:09 - дерандомизация MAX3SAT 01:05:22 - дерандомизация через попарную независимость Дата лекции: Лектор: Мусатов Даниил Владимирович Оператор: Порай Екатерина Монтажёр: Хатымов Ренат Плейлист: