#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

On June 1st, 2026 at 18:30 (Moscow time) we will have a talk by K. Gorbunov and V.A. Lubetsky (in Russian) on the distance between binary trees

К. Горбунов, В.А. Любецкий "Расстояние между бинарными деревьями и эволюция одного дерева относительно другого".

MAF-расстояние между двумя корневыми бинарными деревьями с разметкой листьев одним и тем же множеством имён определяется как минимальное число частей, на которые можно разрезать оба дерева так, чтобы эти части были попарно изоморфны. Доказано, что это расстояние вычисляется алгоритмом квадратичного времени, который допускает мультипликативную ошибку не более 2. Доказательство основано на вложении одного дерева в другое. Наш алгоритм принципиально отличается, как и доказательство, от известных, и проще других, которые основаны на теории двойственности в линейном программировании.