Знаковый ранг и размерность Вапника–Червоненкиса

Исследуется наибольший возможный знаковый ранг знаковых $(N \times N)$-матриц с заданной размерностью Вапника–Червоненкиса $d$. При $d=1$ этот максимум равен трем. При $d=2$ этот максимум имеет порядок $\widetilde{\Theta}(N^{1/2})$. При $d >2$ верны аналогичные, но менее точные утверждения. Нижние оценки улучшают результаты, полученные ранее Бен-Дэвидом с соавторами, верхние оценки являются новыми.
Нижние оценки получены при помощи вероятностных конструкций с использованием теоремы Уоррена из вещественной алгебраической топологии. Верхние оценки получены с использованием результата Вельцля об остовных деревьях с небольшим числом Хелли и с использованием кривой моментов.
Техника верхних оценок также используется: (i) для получения оценок на количество классов заданной размерности Вапника–Червоненкиса и на количество максимальных классов заданной размерности Вапника–Червоненкиса – тем самым получен ответ на вопрос, поставленный Франклем в 1989 г., и (ii) для разработки эффективного алгоритма, вычисляющего приближение знакового ранга с мультипликативной сложностью $O(N/\log(N))$.
Также отмечается общая связь между знаковым рангом и спектральными зазорами, которая основывается на рассуждениях Форстера. Рассмотривается $(N \times N)$-матрица смежности $\Delta$-регулярного графа, где $\Delta \leq N/2$, и ее второе собственное значение по модулю полагается равным $\lambda$. Показано, что знаковый ранг знакового аналога этой матрицы не меньше чем $\Delta/\lambda$. Эта связь используется при доказательстве существования максимального класса $C\subseteq\{\pm 1\}^N$, имеющего размерность Вапника–Червоненкиса $2$ и знаковый ранг $\widetilde{\Theta}(N^{1/2})$. Это дает ответ на вопрос Бен-Дэвида и его соавторов о знаковом ранге больших классов Вапника–Червоненкиса. Также указываются ограничения используемого подхода в духе теоремы Алона–Боппана.
Далее описываются связи с коммуникационной сложностью, геометрией, теорией обучения и комбинаторикой.
Библиография: 69 названий.