Ну что ж, я в целом дошёл до некоторой точки: найденное позавчера новое семейство контрпримеров к гипотезе Диница — Гарга — Гёманса теперь понятно как устроено. Это оказались семейства пересекающихся целочисленных интервалов, которые задают пути до терминалов, точнее, ответвления к терминалам от главной "большой дороги" (в этом семействе до каждого терминала ровно два пути).
В итоге нижняя оценка уже от позавчерашних 1.1397... дошла до 1.28249..., а предел возможного для этого семейства, видимо, 4/3, точнее 4/3 — 1/k для k терминалов в графе, то есть очень большим вычислением можно было бы сделать 4/3 — ε (но надрываться и искать конкретные большие графы уже незачем, нового они ничего не скажут).
Интересно, что начали появляться и структурные результаты, и верхние оценки, и какая-то более-менее стройная теория. Я целый день вчера и утром сегодня старательно всю теорию вычитывал и перепроверял, и мне кажется, что там всё верно. Конечно, я могу ошибаться, но если честно, для структурных результатов это пока не очень принципиально: верхнюю оценку для всех графов мы не получили, оценку 2 для планарных графов не сдвинули, все верхние оценки там по сути для того конкретного семейства, из которого мои контрпримеры. Так что это не очень интересные результаты — хотя мне понравилось, как внезапно возникли не только семейства интервалов, но ещё и двусторонние округления Кнута из девяностых.
А вот нижнюю оценку проверять гораздо проще, а ещё можно перепроверить независимым полным перебором; так что в ней я уверен, и рекорд тут обновился сильно. Всё записали, графы и соответствующие им интервальные семейства нарисовали, препринт я вручную переписал и на Zenodo выложил:
Deletion-Star Ceilings and a 1.28249 Lower Bound for Cost-Preserving Single-Source Unsplittable Flows
(код и сертификаты всё в том же репозитории: https://github.com/snikolenko/unsplittable-flows )
Это была славная охота! Пока немного выдохну, а то вот опять приходится подвинуть обзор игры с пятницы.) Но постараюсь это направление не бросать и всё-таки прийти к каким-нибудь интересным теоремам и, возможно, верхним оценкам, а не только к одному семейству контрпримеров. В твиттер о результате написал, автор оригинального "You should do a breakthrough" Дмитрий Рыбин откликнулся позитивно, так что считаю, что то, что надо было сделать срочно, я уже сделал, а теперь можно спокойно подумать вокруг.
Дивный новый мир! Последние сутки были очень интересные, как в математическую юность свою снова вернулся. Это, конечно, далеко не самый яркий AI-assisted результат из последних пары недель, а всего лишь продолжение чужого прорыва. Например, пока я это всё записывал, новая система от Тенсент сравняла нижнюю оценку экспоненты, связывающей суммы и разности множеств, с верхней, закрыв важный вопрос с 60-летней историей. А задачу о (не)дистиллируемости состояний Вернера (это что-то на квантовом, но тоже очень важно) решили одновременно три группы учёных с разницей в считанные дни, а то и часы. Боюсь, что уже никаких сил не хватит в блоге всё это описывать подробно.
Но это всё равно было очень крутое ощущение. Хочется и продолжать, и повторять.
This is the least sci-fi the world will ever be.
#research #math #ai #publications
В итоге нижняя оценка уже от позавчерашних 1.1397... дошла до 1.28249..., а предел возможного для этого семейства, видимо, 4/3, точнее 4/3 — 1/k для k терминалов в графе, то есть очень большим вычислением можно было бы сделать 4/3 — ε (но надрываться и искать конкретные большие графы уже незачем, нового они ничего не скажут).
Интересно, что начали появляться и структурные результаты, и верхние оценки, и какая-то более-менее стройная теория. Я целый день вчера и утром сегодня старательно всю теорию вычитывал и перепроверял, и мне кажется, что там всё верно. Конечно, я могу ошибаться, но если честно, для структурных результатов это пока не очень принципиально: верхнюю оценку для всех графов мы не получили, оценку 2 для планарных графов не сдвинули, все верхние оценки там по сути для того конкретного семейства, из которого мои контрпримеры. Так что это не очень интересные результаты — хотя мне понравилось, как внезапно возникли не только семейства интервалов, но ещё и двусторонние округления Кнута из девяностых.
А вот нижнюю оценку проверять гораздо проще, а ещё можно перепроверить независимым полным перебором; так что в ней я уверен, и рекорд тут обновился сильно. Всё записали, графы и соответствующие им интервальные семейства нарисовали, препринт я вручную переписал и на Zenodo выложил:
Deletion-Star Ceilings and a 1.28249 Lower Bound for Cost-Preserving Single-Source Unsplittable Flows
(код и сертификаты всё в том же репозитории: https://github.com/snikolenko/unsplittable-flows )
Это была славная охота! Пока немного выдохну, а то вот опять приходится подвинуть обзор игры с пятницы.) Но постараюсь это направление не бросать и всё-таки прийти к каким-нибудь интересным теоремам и, возможно, верхним оценкам, а не только к одному семейству контрпримеров. В твиттер о результате написал, автор оригинального "You should do a breakthrough" Дмитрий Рыбин откликнулся позитивно, так что считаю, что то, что надо было сделать срочно, я уже сделал, а теперь можно спокойно подумать вокруг.
Дивный новый мир! Последние сутки были очень интересные, как в математическую юность свою снова вернулся. Это, конечно, далеко не самый яркий AI-assisted результат из последних пары недель, а всего лишь продолжение чужого прорыва. Например, пока я это всё записывал, новая система от Тенсент сравняла нижнюю оценку экспоненты, связывающей суммы и разности множеств, с верхней, закрыв важный вопрос с 60-летней историей. А задачу о (не)дистиллируемости состояний Вернера (это что-то на квантовом, но тоже очень важно) решили одновременно три группы учёных с разницей в считанные дни, а то и часы. Боюсь, что уже никаких сил не хватит в блоге всё это описывать подробно.
Но это всё равно было очень крутое ощущение. Хочется и продолжать, и повторять.
This is the least sci-fi the world will ever be.
#research #math #ai #publications
❤30👍12🔥10
Маниакальная фаза сменилась депрессивной, надо осмыслить весь этот vibe-mathing... Так что пока возвращаемся к нормальности, вот вам пятничный пост в субботу (как водится, читать лучше по ссылке):
Былина
(и вот на DTF выложил)
“Былина” — стандартная action RPG, которая выезжает на том, что стандартная action RPG про Русь-матушку встречается всё-таки не каждый день. Здесь есть мечи и доспехи, карта и журнал заданий, сундуки, навыки, крафт, подземелья и боссы. И очень, очень много русского духа.
Начинается с того, что молодой воин Сокол отправляется на подвиги и почти сразу погибает. Игра даже выдаёт торжественную надпись “И Сокол умер”, после чего, разумеется, не заканчивается. Героя возвращает к жизни загадочный дух, который теперь делит с ним одно тело (не самый свежий ход, ага). Душу предстоит вернуть, с новым соседом — разобраться, а заодно, раз уж взялся, спасти Тридевятое царство. [...]
Это смесь былин, сказок и современных стереотипов о древней Руси. За одним поворотом стоят деревянные избы и чинные старцы, за другим — огромная разумная жаба [...]
Развесистой клюквы в игре много, собственно, это и есть суть игры. Сокол бродит по осенним лесам, болотам, деревням, подземельям, княжеским палатам и Тридевятому царству. Локации иногда кажутся слишком большими, но всегда стараются показать что-нибудь новое. Мне понравился тёплый деревенский вайб: торговцы, телеги, игра в городки, сервированные столы…
Юмор бывает разный, но обычно довольно детский и построен на помещении сказочных объектов в более реалистичный контекст. Не каждая шутка реально хороша, но в целом создаётся мир в этаком духе русского Пратчетта (у него ведь тоже шутки в основном детские, да и принцип в целом тот же).
Зато иногда герои выражаются весьма не по-детски. Это даже как-то неожиданно было, но тоже добавило колорита. Правда, недетские выражения не озвучены, однажды даже слышал реплику “Иди лесом”, когда написано было нечто совсем другое.
Среди персонажей здесь Василий Пьяница, Жабная Особа и Берёза с глазами. Чтобы поднять уровень, надо обняться с домовёнком; их всех зовут Кузя, и выглядят Кузи о-очень специфически. В общем, думаю, стиль вы поняли. [...]
А вот механически “Былина” очень скромно выглядит. Мы получаем задания, идём по маркеру, разговариваем, дерёмся, собираем добычу, меняем снаряжение и снова идём по маркеру. В журнале есть основные и побочные квесты, в инвентаре — мечи и доспехи, в меню — способности и улучшения. [...] Боссы, кстати, мило сделаны, мне понравились, но это тоже скорее про сеттинг, чем про геймплей.
К счастью, разработчики понимали, что механиками они игрока не удержат, так что, во-первых, постоянно меняют декорации и добавляют сюжет, а во-вторых, разнообразят бои загадками; некоторые загадки вполне даже свежо смотрятся.
А главное, хотя история честно проходит стандартную арку героя, и Сокол успевает обрести характер, завершить своё путешествие и даже завести хозяйство, всё это не затянуто; пройти “Былину” можно и нужно часов за восемь. [...]
Так что ознакомиться можно, для доброй былины может и этого оказаться достаточно.
#tgif #games
Былина
(и вот на DTF выложил)
“Былина” — стандартная action RPG, которая выезжает на том, что стандартная action RPG про Русь-матушку встречается всё-таки не каждый день. Здесь есть мечи и доспехи, карта и журнал заданий, сундуки, навыки, крафт, подземелья и боссы. И очень, очень много русского духа.
Начинается с того, что молодой воин Сокол отправляется на подвиги и почти сразу погибает. Игра даже выдаёт торжественную надпись “И Сокол умер”, после чего, разумеется, не заканчивается. Героя возвращает к жизни загадочный дух, который теперь делит с ним одно тело (не самый свежий ход, ага). Душу предстоит вернуть, с новым соседом — разобраться, а заодно, раз уж взялся, спасти Тридевятое царство. [...]
Это смесь былин, сказок и современных стереотипов о древней Руси. За одним поворотом стоят деревянные избы и чинные старцы, за другим — огромная разумная жаба [...]
Развесистой клюквы в игре много, собственно, это и есть суть игры. Сокол бродит по осенним лесам, болотам, деревням, подземельям, княжеским палатам и Тридевятому царству. Локации иногда кажутся слишком большими, но всегда стараются показать что-нибудь новое. Мне понравился тёплый деревенский вайб: торговцы, телеги, игра в городки, сервированные столы…
Юмор бывает разный, но обычно довольно детский и построен на помещении сказочных объектов в более реалистичный контекст. Не каждая шутка реально хороша, но в целом создаётся мир в этаком духе русского Пратчетта (у него ведь тоже шутки в основном детские, да и принцип в целом тот же).
Зато иногда герои выражаются весьма не по-детски. Это даже как-то неожиданно было, но тоже добавило колорита. Правда, недетские выражения не озвучены, однажды даже слышал реплику “Иди лесом”, когда написано было нечто совсем другое.
Среди персонажей здесь Василий Пьяница, Жабная Особа и Берёза с глазами. Чтобы поднять уровень, надо обняться с домовёнком; их всех зовут Кузя, и выглядят Кузи о-очень специфически. В общем, думаю, стиль вы поняли. [...]
А вот механически “Былина” очень скромно выглядит. Мы получаем задания, идём по маркеру, разговариваем, дерёмся, собираем добычу, меняем снаряжение и снова идём по маркеру. В журнале есть основные и побочные квесты, в инвентаре — мечи и доспехи, в меню — способности и улучшения. [...] Боссы, кстати, мило сделаны, мне понравились, но это тоже скорее про сеттинг, чем про геймплей.
К счастью, разработчики понимали, что механиками они игрока не удержат, так что, во-первых, постоянно меняют декорации и добавляют сюжет, а во-вторых, разнообразят бои загадками; некоторые загадки вполне даже свежо смотрятся.
А главное, хотя история честно проходит стандартную арку героя, и Сокол успевает обрести характер, завершить своё путешествие и даже завести хозяйство, всё это не затянуто; пройти “Былину” можно и нужно часов за восемь. [...]
Так что ознакомиться можно, для доброй былины может и этого оказаться достаточно.
#tgif #games
🔥16❤9👍7
Продолжаем возвращаться к нормальности. Смонтировал и выложил доклад из школы имени Бориса Поляка:
AI Safety в середине 2026 года
(слайды на странице "Выступления")
Это в принципе мой обычный доклад про AI safety, но в данном случае мне понравилось, как получилось. Два часа как раз достаточно, чтобы рассказать по верхам основную логику происходящего и упомянуть пару последних горячих новостей; например, довольно подробно рассказал про J-space. С тех пор, правда, ещё одна горячая новость появилась, но это не то чтобы что-то в докладе отменяет.
Да и аудитория была благодарная, мне вообще на школе Поляка очень понравилось. Особенно, конечно, понравилось, что она в этот раз была в Петербурге; коллеги, спасибо за приглашение и приезжайте ещё! :)
Кстати, с помощью GPT я теперь умею легко и просто добавлять к своим докладам не идеальные, но вполне разумного качества субтитры. И вообще GPT сильно помогает не только с интеллектуальной работой, но и вот, например, с видеомонтажом (хотя, казалось бы, совсем не его модальность). Мир действительно меняется во всех направлениях.
#talks #events #aisafety
AI Safety в середине 2026 года
(слайды на странице "Выступления")
Это в принципе мой обычный доклад про AI safety, но в данном случае мне понравилось, как получилось. Два часа как раз достаточно, чтобы рассказать по верхам основную логику происходящего и упомянуть пару последних горячих новостей; например, довольно подробно рассказал про J-space. С тех пор, правда, ещё одна горячая новость появилась, но это не то чтобы что-то в докладе отменяет.
Да и аудитория была благодарная, мне вообще на школе Поляка очень понравилось. Особенно, конечно, понравилось, что она в этот раз была в Петербурге; коллеги, спасибо за приглашение и приезжайте ещё! :)
Кстати, с помощью GPT я теперь умею легко и просто добавлять к своим докладам не идеальные, но вполне разумного качества субтитры. И вообще GPT сильно помогает не только с интеллектуальной работой, но и вот, например, с видеомонтажом (хотя, казалось бы, совсем не его модальность). Мир действительно меняется во всех направлениях.
#talks #events #aisafety
🔥17❤4👍3👏2
И вот ещё в пандан к предыдущему посту, да и просто о вечном.
В этом году одним из лауреатов премии Филдса стал Яков (Джейкоб) Цимерман (да, с одной "м"). Он родился в Казани, в раннем детстве эмигрировал с семьёй в Канаду, в начале нулевых выигрывал золотые медали IMO, а потом доказал гипотезу Гриффита и гипотезу Андре — Оорта.
Не буду надувать щёки и делать вид, будто я понимаю, о чём это и в чём именно достижение Якова, всё равно дальше определений мы там не продвинемся.
Так вот, к чему я это. Неделю назад, почти сразу после объявления лауреатов Филдсовской медали, Цимерман объявил на пресс-конференции, что "переходит в AI safety" и вскоре присоединится к OpenAI, чтобы над этим работать. Боаз Барак, который уже давно там, "is looking forward (though also more than a bit humbled)". :)
Может показаться, как написал один AI-исследователь, что это "как нанять Лионеля Месси руководителем проектов". Но это не было спонтанным или сугубо финансовым решением. Например, у Цимермана всего три препринта на arXiv. Знаете, как называется последний из них, годичной давности?
A Taxonomy of Omnicidal Futures Involving Artificial Intelligence
В общем, очень здорово, что AI Safety привлекает всё больше по-настоящему серьёзных исследователей. Глядишь, этак у человечества и кое-какие надежды могут появиться. Кстати, Цимерман уже сделал сайт под заманчивым названием, наверное, стоит изучить:
AI Safety for Mathematicians
Времена — они такие.
#aisafety #news #math
В этом году одним из лауреатов премии Филдса стал Яков (Джейкоб) Цимерман (да, с одной "м"). Он родился в Казани, в раннем детстве эмигрировал с семьёй в Канаду, в начале нулевых выигрывал золотые медали IMO, а потом доказал гипотезу Гриффита и гипотезу Андре — Оорта.
Не буду надувать щёки и делать вид, будто я понимаю, о чём это и в чём именно достижение Якова, всё равно дальше определений мы там не продвинемся.
Так вот, к чему я это. Неделю назад, почти сразу после объявления лауреатов Филдсовской медали, Цимерман объявил на пресс-конференции, что "переходит в AI safety" и вскоре присоединится к OpenAI, чтобы над этим работать. Боаз Барак, который уже давно там, "is looking forward (though also more than a bit humbled)". :)
Может показаться, как написал один AI-исследователь, что это "как нанять Лионеля Месси руководителем проектов". Но это не было спонтанным или сугубо финансовым решением. Например, у Цимермана всего три препринта на arXiv. Знаете, как называется последний из них, годичной давности?
A Taxonomy of Omnicidal Futures Involving Artificial Intelligence
В общем, очень здорово, что AI Safety привлекает всё больше по-настоящему серьёзных исследователей. Глядишь, этак у человечества и кое-какие надежды могут появиться. Кстати, Цимерман уже сделал сайт под заманчивым названием, наверное, стоит изучить:
AI Safety for Mathematicians
Времена — они такие.
#aisafety #news #math
❤18🔥11👍5