Какой самый большой разрыв между рангом и приблизительным рангом?

Мы знаем, что log ранга матрицы 0-1 является нижней границей детерминированной сложности связи, а log приблизительного ранга является нижней границей рандомизированной сложности связи. Наибольший разрыв между детерминированной коммуникационной сложностью и рандомизированной коммуникационной сложностью является экспоненциальным. Так как насчет разрыва между рангом и приблизительным рангом булевой матрицы?

co.combinatorics linear-algebra matrices communication-complexity boolean-matrix pyao
источник

что такое «приблизительный ранг» матрицы?

Суреш Венкат

ϵ

$\epsilon$ -approximate ранг булевой матрицы

M

$M$ минимальный ранг реальной матрицы

A

$A$ , что отличается от

M

$M$ не более чем на

ϵ

$\epsilon$ в любой записи (см Бурман и Вольф 2001, «Коммуникационная сложность нижние границы полиномами»). Было бы полезно отредактировать вопрос, чтобы объяснить это (если это желаемое определение) и описать роль

ϵ

$\epsilon$ (поскольку разница в рангах явно зависит от

ϵ

$\epsilon$ ).

mjqxxxx

Сначала я приведу некоторую предысторию и определю приблизительный рейтинг. Хорошим справочным материалом является недавний опрос Ли и Шрайбмана « Нижние границы сложности коммуникации» .

Определение: Пусть - знаковая матрица. Приближенный ранг с коэффициентом аппроксимации , обозначаемый , равен $A$ $A$ $\alpha$ $rank^\alpha(A)$

$rank^\alpha(A)=\min_{B:1\leq A[i,j]\cdot B[i,j] \leq \alpha} rank(B)$

Когда , определите $\alpha\to \infty$

$rank^\alpha(A)=\min_{B:1\leq A[i,j]\cdot B[i,j]} rank(B)$ .

В результате Краузе говорится, что где и - это сложность связи частных монет с ограниченной ошибкой с ошибкой, ограниченной сверху . $R_\epsilon^{pri}(A)\geq \log rank^\alpha(A)$ $\alpha=1/(1-2\epsilon)$ $R_\epsilon^{pri}$ $A$ $\epsilon$

Выше было для фона. Теперь, чтобы ответить на вопрос, Патури и Саймон показали, что полностью характеризует сложность связи с неограниченной ошибкой . Они также показали , что это согласуется с минимальным размером расположения , реализующей булеву функцию, коммуникационная матрица . Сложность связи функции равенства с неограниченной ошибкой равна . Запомни. $rank^\infty(A)$ $A$ $A$ $O(1)$

Матрица связи для равенства - это просто тождество, т. Е. Булева матрица с строками и столбцами со всеми единицами по диагонали. Давайте обозначим это как . Алон показал, что точностью до логарифмического множителя (по теореме Краузе мы получаем ). $2^n$ $2^n$ $I_{2^n}$ $rank^2(I_{2^n})=\Omega(n)$ $R_\epsilon^{pri}(EQ)=\Omega(\log n)$

Тождественная матрица имеет полный ранг, т. Е. . Таким образом, мы имеем экспоненциально большие разделения для и . $2^n$ $\alpha=2$ $\alpha\to\infty$

Маркос Вильягра
источник

Спасибо. но мой вопрос: есть ли суперэкспоненциальный разрыв для и , где но не .

r a n k (A)

$rank(A)$

r a n k^{α} (A)

$rank^{\alpha}(A)$

α > 1

$\alpha>1$

α \neq \infty

$\alpha\neq\infty$

Пяо

ааа я вижу, но это не написано в вопросе. Насколько мне известно, самый большой разрыв является экспоненциальным.

Маркос Вильягра

Маркос дает вам ссылку, которая показывает разрыв в между и . как может быть суперэкспоненциальный разрыв, когда размер матрицы равен ?

2^{n} / n

$2^n/n$

r a n k

${rank}$

{r a n k}^{2}

${rank}^2$

2^{n}

$2^n$

Сашо Николов

Вы имеете в виду разрыв а не

Ω (2^{n})

$\Omega(2^n)$

2^{Ω (n)}

$2^{\Omega(n)}$

Сашо Николов

Сашо делает хорошую мысль, что вы имеете в виду под «суперэкспоненциальным»? Для любой проблемы со связью матрица всегда больше

{0, 1}^{n} \times {0, 1}^{n}

$\{0,1\}^n \times \{0,1\}^n$ .

Маркос Вильягра

Какой самый большой разрыв между рангом и приблизительным рангом?

Ответы: