Жесткость матриц и использование матриц с низкой жесткостью

Грубо говоря, матрица ранга называется жесткой, если уменьшить ее ранг до $n$ , необходимо изменитькрайней мереп1+еего записи, для некоторыхх>0.$\frac{n}{2}$$n^{1+\epsilon}$$\epsilon > 0$

Если матрица A размером является жесткой, то наименьшая прямолинейная программа, вычисляющая A x ( x - это вектор размера n ), имеет либо суперлинейный размер, либо супер логарифмическую глубину.$n \times n$$A$$Ax$$x$$n$

Есть ли обратное утверждение к приведенному выше утверждению?

Другими словами, есть ли смысл использовать нетривиальные и неочевидные матрицы полной жесткости полного ранга в TCS?

Есть ли понятие жесткости для матриц с более низкими рангами (скажем, для некоторой константыв)?$\frac{n}{c}$$c$

не имея дополнительного разъяснения вопроса, вот попытка / набросок ответа. Жесткость матрицы имеет глубокие связи с фундаментальными вопросами теории TCS / сложности, включая нижние границы схем, [1] и, следовательно, разделение классов сложности, и теорию кодирования [2], а также другие области. [5] хороший обзор слайдов.

термины «низкий» и «высокий» в отношении жесткости матриц используются неформально, а не в точно определенном техническом смысле. [хотя Фридман определил «сильную» жесткость. [6]] известно, что случайные матрицы имеют высокую жесткость, но в основном это открытая проблема в этой области, которой уже 3,5 десятилетия, для явного построения любой матрицы со «значительно высокой» жесткостью.

вопрос далее не определяет / не уточняет субъективные термины «нетривиальный» или «неочевидный» и займет там некоторую свободу.

в этой области проводится исследование, посвященное жесткости матриц Адамара, которые используются / применяются в разных областях теории кодирования и в других местах.

кажется справедливым сказать, что доказуемо высокий результат жесткости превзошел бы порог, приводящий, по крайней мере, к «новым нетривиальным следствиям в теории сложности», но самых известных оценок для матриц Адамара недостаточно. [3] но это также не доказывает, что они имеют ограниченную «низкую» жесткость. в основном та же самая история с матрицами Вандермонда [также приложения в теории кодирования], рассмотренные Lokam. [4]

Итак, подводя итог всему, что можно сказать, так это то, что «слабые оценки нижней жесткости» были доказаны на некоторых матрицах, включая матрицы Адамара / Вандермонда.

в этой области также отсутствуют опубликованные численные эксперименты, оценки или алгоритмы.

[1] Сложность булевой функции, Стасис Юкна, 2011, с. 12.8 «Жесткие матрицы требуют больших цепей»

[2] О матричной жесткости и локально самокорректирующихся кодах Зеев Двир

[3] Улучшение нижних оценок ригидности матриц Адамара Кашин / Разборов

[4] О жесткости матриц Вандермонда Локам

[5] Махди Черагчи говорит о жесткости матрицы

[6] Дж. Фридман. Примечание о жесткости матрицы. Combinatorica, 13 (2); 235-239, 1993