Недавнее и невероятно приятное доказательство гипотезы о чувствительности основано на явном * построении матрицы An∈{−1,0,1}2n×2nAn∈{−1,0,1}2n×2nA_n\in\{-1,0,1\}^{2^n\times 2^n} , определенной рекурсивно следующим образом: A1=(0110)A1=(0110)A_1 = \begin{pmatrix} 0&1\\1&0\end{pmatrix} и, для, В...
Каковы наиболее практически эффективные алгоритмы умножения двух очень разреженных логических матриц (скажем, N = 200 и всего 100-200 ненулевых элементов)? На самом деле, у меня есть преимущество в том, что когда я умножаю A на B, B заранее определены, и я могу выполнять произвольную сложную...
Мы знаем, что log ранга матрицы 0-1 является нижней границей детерминированной сложности связи, а log приблизительного ранга является нижней границей рандомизированной сложности связи. Наибольший разрыв между детерминированной коммуникационной сложностью и рандомизированной коммуникационной...
Во время моей работы я столкнулся со следующей проблемой: Я пытаюсь найти -матрицу , для любого , со следующими свойствами:n×nn×nn \times n (0,1)(0,1)(0,1)MMMn>3n>3n > 3 Определитель четен.MMM Для любых непустых подмножеств с, Подматрица имеет нечетный детерминанту тогда и только тогда ,...