Untergrenze für Determinante und Permanent

22

In Anbetracht der jüngsten Kluft bei Tiefe-3 ergibt sich (was unter anderem eine Tiefen-3-Arithmetikschaltung für die Determinante über ergibt ), Ich habe folgende Fragen: Grigoriev und Karpinski haben eine Untergrenze für jede arithmetische Tiefen-3-Schaltung bewiesen, die die Determinante von Matrizen über endlichen Feldern berechnet (was ich vermute, gilt auch für die Permanent). Die Ryser-Formel zur Berechnung der bleibenden Zahl liefert eine arithmetische Schaltung der Tiefe 3 der Größen×nC2&OHgr;(n)n×nO(n22n)=2O(n)2nlognn×nC2Ω(n)n×nO(n22n)=2O(n). Dies zeigt, dass das Ergebnis für Schaltkreise der Tiefe 3 für die permanenten über endlichen Felder im Wesentlichen eng ist. Ich habe zwei Fragen:

1) Gibt es eine Formel der Tiefe 3 für die Determinante analog zur Ryser-Formel für die bleibende Karte?

2) Ergibt eine Untergrenze für die Größe der Arithmetikkreise, die das Determinantenpolynom \ textit {immer} berechnen, eine Untergrenze für das Permanente Polynom? (Über handelt es sich um dieselben Polynome).F2

Obwohl sich meine Frage aktuell auf diese Polynome über endliche Felder bezieht, möchte ich auch den Status dieser Fragen über beliebige Felder wissen.

Nikhil
quelle
3
Das ist interessant ... kürzlich ( eccc.hpi-web.de/report/2013/026 ) wurde eine -Obergrenze über die komplexen Zahlen bewiesen. Es gibt also irgendwie einen großen Unterschied zwischen charakteristischen Null- und Endlichen Feldern ...2O(n1/2logn)
Ryan Williams
Ich hätte das neue Ergebnis erwähnen sollen. Ich habe die Zeitung gelesen und wollte wissen, was sich aus bekannten Ergebnissen für den Fall des endlichen Feldes ableiten lässt. Aktualisiert die Frage, um das Papier einzuschließen.
Nikhil
Gibt es eine ähnliche Untergrenze für Determinante / Permanent bei Stromkreisen mit Tiefe 3 über Feldern mit der Charakteristik Null?
Gorav Jindal
Über dem Merkmal Null, AFAIK, ist die beste Untergrenze für die elementare symmetrische Funktion (und auch das Determinantenpolynom) nach Shpilka und Wigderson. Überprüfen Sie cs.technion.ac.il/~shpilka/publications/…Ω(n2)
Nikhil

Antworten:

11

Permanent ist für VNP unter p-Projektionen für alle Felder, die nicht zu Merkmal 2 gehören, vollständig. Dies gibt eine positive Antwort auf Ihre zweite Frage. Wenn diese Reduzierung linear wäre, gäbe es eine positive Antwort auf Ihre erste Frage, aber ich glaube, das bleibt offen.

gesagt: Es gibt ein Polynom so dass eine Projektion von , dh es gibt eine bestimmte Substitution, die jede Variable entweder an eine Variable sendet oder eine solche Konstante, dass nach dieser Substitution die Determinante permanent die Determinante berechnet .d e t n ( X ) p e R m q ( n ) ( Y ) y i j x k l q ( n ) × Q ( n ) n × nq(n)detn(X)permq(n)(Y)yijxkq(n)×q(n)n×n

1) Somit ergibt die Ryser-Formel eine Tiefe-3-Formel (Tiefe nimmt unter Projektionen nicht zu, da die Substitutionen an den Eingangsgattern durchgeführt werden können) der Größe für die Determinante. UPDATE : Wie @Ramprasad in den Kommentaren ausführt, gibt dies nur dann etwas Nichttriviales, wenn , da es eine triviale Formel für Tiefe 2 der Größe für det. Ich bin mit Ramprasad darin, dass das Beste, was ich weiß, die Reduktion durch ABPs ist, die ergibt . q ( n ) = o ( n log n ) n n ! = 2 O ( n log n ) q ( n ) = O ( n 3 )2O(q(n))q(n)=o(nlogn)nn!=2O(nlogn)q(n)=O(n3)

2) Kann das permanent durch eine Schaltung der Größe über ein Feld der Charakteristik nicht 2 berechnet werden , dann kann die Determinante durch eine Schaltung der Größe berechnet werden . Eine untere Schranke von für die Schaltungsgröße für ergibt also eine untere Schranke von für die Schaltungsgröße für die bleibende (das ist invers , nicht ). Das oben erwähnte ergibt eine untere Grenze von perm von einer unteren Grenze von det.m×ms(m)n×ns(q(n))b(n)detnb(q1(n))q 1/q(n)q(n)=O(n3)b(n1/3)b(n)

Joshua Grochow
quelle
6
Ich möchte nur darauf hinweisen, dass die Determinante, die eine Projektion einer polynomiell größeren bleibenden Karte ist, nicht viel ergibt. Die Determinante hat natürlich ein trivialesGröße Schaltung. Selbst wenn man also zeigt, dass die Determinante eine Projektion einer bleibenden erhält man mit Rysers Formel nichts Nicht-Triviales. Ich denke, für Ihre Beweisstrategie muss man zeigen, dass , aber ich sehe nicht, wie man dies aus der üblichen Reduktion herausholt. AFAIK, keine Schaltung der Tiefe 3 asymptotisch kleiner alsist bekannt für die Determinante über endliche Felder. n × n n 2 × n 2 q ( n ) = O ( n ) n !n!n×nn2×n2q(n)=O(n)n!
Ramprasad
@Ramprasad: Es gibt eine Projektion von auf im allgemeinen Fall über beliebige Felder, oder? Die Umsetzung dieser Reduzierung der Tiefe 3 ist also die Hürde - ist es das, was Sie meinen? P E R M O ( n )DETnPERMO(n)
Nikhil
1
@ Nikhil: Gibt es so eine Projektion ?! Wenn das wahr wäre, hätten wir natürlich sofort einen Tiefen-3-Schaltkreis für die Determinante, indem wir nur die Ryser-Formel verwenden (die vor dem Abgrund-zu-Tiefen-3-Ergebnis nicht bekannt war) ). Die einzige Reduktion, die ich kenne, besteht darin, den ABP für die Determinante (die -groß ist) zu nehmen und diesen als Projektion einer bleibenden Größe von schreiben . Ich wäre sehr überrascht von einer Reduzierung auf -große permanente Griffe. O ( n 3 ) O ( n 3 ) O ( n )2O(n)O(n3)O(n3)O(n)
Ramprasad
1
Ich bin mir ziemlich sicher, dass dies ein Tippfehler im Artikel ist (aber ich werde mich trotzdem bei Manindra erkundigen). Avi Wigdersons Vortrag (PPT) zum 60. Geburtstag von Valiant ist einer der Orte, an denen die Verbesserung vonFür die Tiefe 3 war die Komplexität der Determinante unbekannt. Tiefen-3-Kreise über endlichen Feldern sind ein merkwürdiges Beispiel, bei dem die beste Obergrenze für die bleibende Karte kleiner als die Determinante ist! n!
Ramprasad
1
Lassen Sie uns diese Diskussion im Chat fortsetzen
Ramprasad
11

Es ist sehr wahrscheinlich, dass die Determinante in gewisser Weise härter ist als die bleibende. Sie sind beide Polynome, der Waring Rank (Summen von n Potenzen linearer Formen) der bleibenden Karte ist ungefähr 4 ^ n, der Chow Rank (Summen von Produkten linearer Formen) ist ungefähr 2 ^ n. Es ist klar, Waring Rank \ leq 2 ^ {n-1} Chow Rank. Für die Determinante sind diese Zahlen nur Untergrenzen. Andererseits habe ich vor einiger Zeit bewiesen, dass der Waring-Rang der Determinante durch (n + 1) nach oben begrenzt ist! und dies könnte nahe an der Wahrheit liegen.

Leonid Gurvits
quelle
7
Ich habe die Werbung entfernt.
Jeffs
3
Können Sie die Referenz für den Beweis geben?
Kaveh