Пятеро исследователей — Чаттерджи, Гош, Гурджар, Радж и Тирауф — выложили крупную статью на ECCC. Они утверждают, что задача Bipartite Matching решается в классе NC. Простыми словами: это поиск идеальных пар из двух групп, который можно распараллелить так, чтобы время работы росло полилогарифмически (log(n) в степени). Если доказательство подтвердится, это закроет проблему, висевшую с 1980-х годов.
Сама задача Bipartite Matching сводится к подбору пар, когда все участники строго делятся на две группы и ищут только гетеросексуальные пары. Ещё в 1980-х Карп, Апфал и Вигдерсон, а затем другая команда — Мулмулей, Умеш Вазирани и Виджай Вазирани — показали, что её можно решить быстро на параллельных процессорах, но с оговоркой: процессорам нужны случайные биты. Новый результат — они избавились от случайности. Теперь тот же самый алгоритм (Mulmuley-Vazirani-Vazirani) работает детерминированно. Это значит, что задачи 1 и 2 (проверка существования паросочетания и его построение) лежат в классе NC.
Автор блога честно признаётся, что ещё не разобрался в доказательстве и надеется, что кто-то объяснит в комментариях. Он предлагает попросить AI сгенерировать summary, если лень читать 50 страниц.
Вторая часть поста — политическая. Сегодня в Нью-Йорке проходят праймериз. Умные друзья автора, работающие в AI safety, очень взволнованы кампанией Алекса Бореса из 12-го округа Нью-Йорка (центральный Манхэттен). Борес — один из главных сторонников регулирования AI на федеральном уровне. Против него анти-регуляторный PAC Марка Андриссена “Leading the Future” потратил миллионы долларов. В остальном Борес описывается как «умеренный демократ», умереннее своей базы по Израилю. Автор призывает голосовать за него, если читатели живут в этом округе и заботятся о безопасности ИИ.