Circuit lower bounds and linear codes

В 1977 году Вэлиант предложил использующий теорию графов метод доказательства нижних оценок для алгебраических схем с гейтами, вычисляющими линейные функции. Он использовал этот метод для сведения задачи доказательства нижних оценок для таких схем к доказательству нижних оценок на жесткость матрицы, понятие о которой он ввел в своей статье. Наилучшая нижняя оценка для матрицы, заданной в явном виде, принадлежит Дж. Фридману (1993), который доказал нижнюю оценку для матриц, порождающих коды, исправляющие ошибки, над конечным полем. Он показал, что это доказательство может быть интерпретировано как оценка некоторого параметра, определенного для всех конечномерных линейных пространств. В этой заметке мы определяем другой параметр, который может быть использован для доказательства нижних оценок на схемы с линейными гейтами. Наш параметр может быть больше параметра Фридмана и, по-видимому, несравним с жесткостью. Таким образом, доказать нижние оценки при помощи этого понятия может оказаться проще. Библ. – 14 назв.