In this talk I will focus on two seemingly different directions in modern algorithmic group theory: finding more and more efficient algorithms and how to find "hard" instances of the problems, how to amplify hardness, and how to measure hardness of the algorithms. The talk is intended to be non-technical, I will emphasize some relations between algorithmic group theory and cryptography.

Задача о максимальном потоке и её двойственная -- задача о минимальном разрезе -- являются одними из наиболее изучаемых задач теории графов, на практике эти задачи часто встречаются в качестве промежуточных вычислений. В отдельных случаях возникает потребность решения задачи о максимальном потоке на вычислительной распределенной сети, где графом является топология взаимодействия этой сети. В таких ситуациях возникает вопрос: а можно ли решить задачу о максимальном потоке методом, не требующим синхронизации или сбора всей информации на одном из узлов сети? Алгоритмы, решающие какую-либо задачу в сети с такими ограничениями, обычно называются "распределенными". Как пример, задача синхронизации времени в сети допускает только распределенные методы решения. В докладе пойдет речь об одном распределенном алгоритме решения задачи о максимальном потоке и его связи с методами, основанными на электрических потоках и решении лапласиановых систем.

Следуя Н.Пиппенжеру, можно сказать, что наиболее общие "законы теории информации" выражаются в терминах линейных неравенств для энтропии Шеннона. Классические неравенства для энтропии (монотонность, субаддитивность, субмодулярность) восходят к работе К.Шеннона 1948 г. Эти неравенства имеют ясный интуитивный смысл. Например, субаддитивность энтропии $H(X,Y) \le H(X)+H(Y)$ означает, что "количество информации", заключенное в паре случайных величин (X,Y), не превосходит суммы объемов информации в X и Y соответственно. Известны многочисленные применения информационных неравенств. Каждое линейное неравенство для энтропии можно эквивалентным образом переформулировать на многих разных языках: как утверждения о конечных группах, о колмогоровской сложности, о размерах проекций конечных множеств, и т.д.

Известны и более экзотические утверждения о шенноновской энтропии -- так называемые условные информационные неравенства (constraint information inequalities). Каждое такое неравенство выполнено при некотором ограничении на рассматриваемые случайные величины. Например, неравенство Инглетона для энтропий четверки случайных величин (A,B,C,D) выполняется при условии I(A:B) = I(A:B|C) = 0. Известно лишь несколько нетривиальных примеров условных информационных неравенств, и до недавнего времени они казались бессодержательными артефактами определения энтропии.

Мы покажем, что условные информационные неравенства могут иметь вполне содержательный смысл и интересные применения. Мы обсудим связь условных неравенств с теоремой Матуша (конус энтропийных точек не полиэдрален), с бикликовым покрытием графа (оценки Куликова--Юкны) и некоторыми оценками для раскраски графов (Верещагин--Касед).