Rigidité matricielle et utilisations de matrices à faible rigidité

On dit qu'en gros une matrice de rang est rigide, si pour ramener son rang à , il faut changer au moins de ses entrées, pour certains . $n$ $\frac{n}{2}$ $n^{1+\epsilon}$ $\epsilon > 0$

Si une matrice est rigide, alors le plus petit programme en ligne droite calculant ( est un vecteur de taille ) est soit de taille super-linéaire, soit de profondeur super logarithmique. $n \times n$ $A$ $Ax$ $x$ $n$

Y a-t-il un contraire à la déclaration ci-dessus?

En d'autres termes, y a-t-il des utilisations de matrices de faible rigidité non triviales et non évidentes de rang complet dans TCS?

Existe-t-il une notion de rigidité pour les matrices de rangs inférieurs (disons pour une constante )? $\frac{n}{c}$ $c$

cc.complexity-theory T ....
la source

+1, agréable de voir la question sur la rigidité ici, sujet avancé, mais ce n'est pas si clair. l'inverse de l'énoncé serait quelque chose comme si le plus petit programme en ligne droite calculant est soit de taille superlinéaire soit de profondeur superlogarithmique, alors la matrice est rigide. droite? mais cela semble être différent de la dernière question sur les matrices de faible rigidité non triviales / non évidentes. il semblerait que la rigidité de la plupart des matrices, faible ou élevée, n'est pas si triviale ou évidente ... il existe de nombreuses matrices utiles qui ont une faible rigidité ... aucune matrice non aléatoire de rigidité élevée n'a été construite!

A x

$A x$

n \times n

$n \times n$

vzn

Si une matrice n'est pas rigide, vous pouvez la décomposer comme où est une matrice de bas rang et est une matrice clairsemée. Les programmes linéaires définis par et peuvent être calculés efficacement (c'est-à-dire mieux que triviaux) en s'appuyant sur les propriétés de faible rang et de faible densité. Cela signifie, par exemple, que si nécessite un circuit de taille quadratique, il doit alors être rigide (avec un choix approprié des paramètres).

A

$A$

A = B + C

$A=B+C$

B

$B$

C

$C$

B

$B$

C

$C$

A

$A$

Mahdi Cheraghchi

peut-être d'abord qu'il est bon de demander des exemples de matrices avec une rigidité non évidemment faible

Sasho Nikolov

@vzn une autre façon d'énoncer l'inverse est "les matrices à faible rigidité ont-elles de petits circuits linéaires". votre réponse est exactement dans la direction opposée (pas un mot sur les applications du genre moins rigides -> plus efficaces), donc -1

Sasho Nikolov

@MCH Bon point. Quoi de mieux que de trivial? Vous soulevez un point intéressant. Je vais changer un peu la question.

T ....

Réponses:

-3

faute de précisions supplémentaires sur la question, voici un essai / esquisse d'une réponse. la rigidité de la matrice a des liens profonds avec les questions fondamentales de la théorie TCS / complexité, y compris les limites inférieures des circuits, [1] et donc les séparations de classes de complexité, et la théorie du codage [2] ainsi que d'autres domaines. [5] est une belle enquête sur diapositives.

les termes "faible" et "élevé" en référence à la rigidité des matrices sont utilisés de manière informelle et non dans un sens technique défini avec précision. [bien que Friedman ait défini une rigidité "forte". [6]] les matrices aléatoires sont connues pour avoir une rigidité élevée mais, fondamentalement, c'est ~ un problème ouvert vieux de 3,5 décennies dans ce domaine pour construire explicitement toute matrice avec une rigidité "significativement élevée".

la question ne définit / clarifie pas davantage les termes subjectifs "non triviaux" ou "non évidents" et y prendra une certaine liberté.

dans ce domaine, il existe une ligne de recherche sur la rigidité des matrices Hadamard qui ont des utilisations / applications diverses en théorie du codage et ailleurs.

il semble juste de dire qu'un résultat de rigidité prouvablement élevé dépasserait le seuil de conduire au moins à de "nouveaux corollaires non triviaux dans la théorie de la complexité", mais les limites les plus connues sur les matrices de Hadamard ne suffisent pas. [3] mais cela ne prouve pas non plus de façon concluante qu'ils ont une rigidité "faible" limitée. c'est fondamentalement la même histoire avec les matrices Vandermonde [également des applications dans la théorie du codage] considérées par Lokam. [4]

ainsi, pour résumer tout ce qui peut être dit, c'est que des "limites de rigidité inférieure faibles" ont été prouvées sur certaines matrices, notamment les matrices Hadamard / Vandermonde.

il ne semble pas non plus qu'il y ait d'expériences, d'estimations ou d'algorithmes numériques publiés dans la région.

[1] Complexité de la fonction booléenne par Stasys Jukna, 2011, sec 12.8 "les matrices rigides nécessitent de grands circuits"

[2] Sur la rigidité de la matrice et les codes auto-corrigés localement Zeev Dvir

[3] Amélioration des limites inférieures sur la ridicule des matrices Hadamard Kashin / Razborov

[4] Sur la rigidité des matrices Vandermonde Lokam

[5] Discussion sur la rigidité de la matrice de Mahdi Cheraghchi

[6] J. Friedman. Une note sur la rigidité de la matrice. Combinatorica, 13 (2); 235-239, 1993

vzn
la source