Двусторонняя коммуникационная сложность функций типа суммы при информировании одного процессора

Асимметричная двусторонняя коммуникационная сложность функции является мерой минимального количества информации, требуемой для обмена двум участникам для того, чтобы один из них смог вычислить значение функции при входах, предоставляемых этими участниками. Мы предлагаем довольно тонкие нижние оценки для этого количества, описываемые через ранг некоторого матричного преобразования таблицы функции. Для некоторых функций типа суммы, таких как метрики Хэмминга, Ли и Такси, они являются даже точными. Мы подчеркиваем, что для этого класса функций обычный log rank таблицы функции дает, вообще говоря, плохую нижнюю оценку.