Kekakuan matriks dan penggunaan matriks dengan kekakuan rendah

Secara kasar matriks peringkat dikatakan kaku, jika menurunkan peringkatnya menjadi $n$ , kita harus mengubah setidaknyadari entri, untuk beberapa. $\frac{n}{2}$ $n^{1+\epsilon}$ $\epsilon > 0$

Jika matriks kaku, maka program garis lurus terkecil yang mengkomputasi ( adalah vektor ukuran ) adalah ukuran super-linear, atau memiliki kedalaman logaritmik super. $n \times n$ $A$ $Ax$ $x$ $n$

Apakah ada kebalikan dari pernyataan di atas?

Dengan kata lain apakah ada kegunaan untuk matriks kekakuan rendah non-sepele dan tidak jelas peringkat penuh di TCS?

Apakah ada gagasan tentang kekakuan untuk matriks dengan peringkat lebih rendah (katakanlah untuk beberapa konstanta)? $\frac{n}{c}$ $c$

cc.complexity-theory T ....
sumber

A x

$A x$

n \times n

$n \times n$

A

$A$

A = B + C

$A=B+C$

B

$B$

C

$C$

B

$B$

C

$C$

A

$A$

mungkin pertama-tama ada baiknya untuk meminta contoh matriks dengan kekakuan yang tidak jelas rendah

Sasho Nikolov

@vzn cara lain untuk menyatakan yang sebaliknya adalah "lakukan matriks kekakuan rendah memiliki sirkuit kecil linier". jawaban Anda persis di arah yang berlawanan (tidak sepatah kata pun tentang aplikasi semacam itu kurang kaku -> lebih efisien), jadi -1

Sasho Nikolov

@MCH Poin bagus. Apa yang bisa lebih baik daripada hal sepele? Anda membuat poin yang menarik, saya akan sedikit mengubah pertanyaan.

T ....

kurang klarifikasi lebih lanjut dari pertanyaan ini, inilah usaha / sketsa jawaban. kekakuan matriks memiliki koneksi yang mendalam ke pertanyaan mendasar dalam teori kompleksitas / TCS termasuk rangkaian batas bawah, [1] dan dengan demikian pemisahan kelas kompleksitas, dan teori pengkodean [2] serta area lainnya. [5] adalah survei slide yang bagus.

istilah "rendah" dan "tinggi" mengacu pada kekakuan matriks digunakan secara informal dan tidak dalam pengertian teknis yang didefinisikan secara tepat. [Meskipun Friedman mendefinisikan kekakuan "kuat". [6]] matriks random diketahui memiliki kekakuan yang tinggi tetapi pada dasarnya, yang ~ masalah terbuka berusia 3,5 dekade di daerah ini secara eksplisit membangun setiap matriks dengan kekakuan "cukup tinggi".

pertanyaannya tidak lebih jauh mendefinisikan / memperjelas istilah subyektif "nontrivial" atau "nonobvious" & akan mengambil kebebasan di sana.

di bidang ini ada garis penelitian melihat kekakuan matriks Hadamard yang memiliki misc menggunakan / aplikasi dalam teori pengkodean & di tempat lain.

tampaknya adil untuk mengatakan hasil kekakuan yang terbukti tinggi akan melampaui ambang batas memimpin setidaknya untuk "akibat wajar baru dalam teori kompleksitas" tetapi batas-batas yang paling dikenal pada matriks Hadamard tidak cukup. [3] tetapi juga tidak secara meyakinkan membuktikan bahwa mereka memiliki kekakuan "rendah" yang terbatas. pada dasarnya cerita yang sama dengan matriks Vandermonde [juga aplikasi dalam teori pengkodean] dipertimbangkan oleh Lokam. [4]

jadi untuk meringkas tentang semua yang dapat dikatakan adalah bahwa "batas kekakuan rendah yang lemah" telah terbukti pada beberapa matriks termasuk matriks Hadamard / Vandermonde.

tampaknya juga tidak ada eksperimen numerik, perkiraan, atau algoritme yang dipublikasikan di area tersebut.

[1] Kompleksitas Fungsi Boolean oleh Stasys Jukna, 2011, detik 12.8 "matriks kaku memerlukan sirkuit besar"

[2] Pada kekakuan matriks dan kode yang dapat dikoreksi sendiri secara lokal, Zeev Dvir

[3] Peningkatan batas bawah pada kekeruhan matriks Hadamard Kashin / Razborov

[4] Tentang Kekakuan Matriks Vandermonde Lokam

[5] Mahdi Cheraghchi berbicara tentang kekakuan matriks

[6] J. Friedman. Catatan tentang kekakuan matriks. Combinatorica, 13 (2); 235-239, 1993

vzn
sumber

Kekakuan matriks dan penggunaan matriks dengan kekakuan rendah

Jawaban: