Apa kesenjangan terbesar antara peringkat dan perkiraan peringkat?

Kita tahu bahwa log dari peringkat matriks 0-1 adalah batas bawah dari kompleksitas komunikasi deterministik, dan log dari peringkat perkiraan adalah batas bawah dari kompleksitas komunikasi acak. Kesenjangan terbesar antara kompleksitas komunikasi deterministik dan kompleksitas komunikasi acak adalah eksponensial. Jadi bagaimana dengan kesenjangan antara peringkat dan perkiraan peringkat dari matriks boolean?

co.combinatorics linear-algebra matrices communication-complexity boolean-matrix pyao
sumber

apa "peringkat perkiraan" dari matriks?

Suresh Venkat

Peringkat

ϵ

$\epsilon$ -roksimasi dari matriks boolean

M

$M$ adalah peringkat minimum dari matriks nyata

A

$A$ yang berbeda dari

M

$M$ paling banyak

ϵ

$\epsilon$ dalam entri apa pun (lih. Buhrman dan Wolf 2001, "Kompleksitas komunikasi lebih rendah oleh polinomial"). Akan sangat membantu untuk mengedit pertanyaan untuk menjelaskan ini (jika itu definisi yang diinginkan) dan menggambarkan peran

ϵ

$\epsilon$ (karena perbedaan peringkat jelas tergantung pada

ϵ

$\epsilon$ ).

mjqxxxx

Pertama saya akan memberikan beberapa latar belakang dan menentukan perkiraan peringkat. Referensi yang baik adalah survei terbaru oleh Lee dan Schraibman Lower Bounds on Communication Complexity .

Definisi: Biarkan menjadi matriks tanda. Peringkat perkiraan dengan faktor aproksimasi , dilambangkan , adalah $A$ $A$ $\alpha$ $rank^\alpha(A)$

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

Saat , tentukan $\alpha\to \infty$

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

Hasil oleh Krause mengatakan bahwa mana dan adalah dibatasi-kesalahan pribadi-koin kompleksitas komunikasi dengan kesalahan atas-dibatasi oleh . $R_\epsilon^{pri}(A)\geq \log rank^\alpha(A)$ $\alpha=1/(1-2\epsilon)$ $R_\epsilon^{pri}$ $A$ $\epsilon$

Di atas adalah untuk latar belakang. Sekarang untuk menjawab pertanyaan, Paturi dan Simon menunjukkan bahwa benar-benar mencirikan kompleksitas komunikasi tak terbatas-kesalahan . Mereka juga menunjukkan bahwa hal ini sesuai dengan dimensi minimum pengaturan mewujudkan fungsi boolean yang matriks komunikasi adalah . Kompleksitas komunikasi unbounded-error dari fungsi kesetaraan adalah . Ingatlah itu. $rank^\infty(A)$ $A$ $A$ $O(1)$

Matriks komunikasi untuk persamaan hanyalah identitas, yaitu, matriks boolean dengan baris dan kolom dengan semua yang ada di diagonal. Mari kita tunjukkan ini dengan . Alon menunjukkan bahwa yang mendekati faktor logaritmik (dengan teorema oleh Krause kita memperoleh ). $2^n$ $2^n$ $I_{2^n}$ $rank^2(I_{2^n})=\Omega(n)$ $R_\epsilon^{pri}(EQ)=\Omega(\log n)$

Matriks identitas memiliki peringkat penuh, yaitu . Dengan demikian, kami memiliki pemisahan besar secara eksponensial untuk dan . $2^n$ $\alpha=2$ $\alpha\to\infty$

Marcos Villagra
sumber

Terima kasih. tetapi pertanyaan saya adalah apakah ada kesenjangan superexponential untuk dan , di mana tetapi bukan .

r a n k (A)

$rank(A)$

r a n k^{α} (A)

$rank^{\alpha}(A)$

α > 1

$\alpha>1$

α \neq \infty

$\alpha\neq\infty$

pyao

Aku mengerti, tapi itu tidak tertulis dalam pertanyaan. Setahu saya, kesenjangan terbesar adalah eksponensial.

Marcos Villagra

Marcos memberi Anda referensi yang menunjukkan celah antara dan . bagaimana bisa ada kesenjangan superexponential ketika ukuran matriks adalah ?

2^{n} / n

$2^n/n$

r a n k

${rank}$

{r a n k}^{2}

${rank}^2$

2^{n}

$2^n$

Sasho Nikolov

maksud Anda celah daripada ?

Ω (2^{n})

$\Omega(2^n)$

2^{Ω (n)}

$2^{\Omega(n)}$

Sasho Nikolov

Sasho membuat poin yang baik, apa yang Anda maksud dengan "super-eksponensial? Untuk masalah komunikasi apa pun, matriks selalu lebih dari .

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

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

Marcos Villagra

Apa kesenjangan terbesar antara peringkat dan perkiraan peringkat?

Jawaban: