Dolna granica wyznacznika i wartości stałej

22

W świetle niedawnej otchłani na głębokości 3 wynik (który między innymi daje głębokości 3 arytmetyczna obieg donxndeterminant naC) I mają następujące pytania: Grigoriev i Karpińskiokazałosię2omów(n)dolna granica dla każdego arytmetyczna obwodu głębokości-3 obliczeniowej wyznacznikanxnmacierze nad polami skończonymi (które, jak sądzę, dotyczą również Stałych). Wzór Ryserana obliczenie Stałego daje obwód arytmetyczny o głębokości-3 o wielkościO(n22n)=2O(2nlognn×nC2Ω(n)n×n . To pokazuje, że wynik jest zasadniczo ścisły dla obwodów o głębokości 3 dla stałych na polach skończonych. Mam dwa pytania:O(n22n)=2O(n)

1) Czy istnieje wzór na głębokość-3 dla wyznacznika analogiczny do wzoru Rysera na stałe?

2) Czy dolna granica wielkości obwodów arytmetycznych obliczających wielomian determinantowy \ textit {always} daje dolną granicę dla wielomianu stałego? (Powyżej są to te same wielomiany).F2

Chociaż moje aktualne pytanie dotyczy tych wielomianów na polach skończonych, chciałbym również poznać status tych pytań na polach arbitralnych.

Nikhil
źródło
3
To ciekawe .... niedawno ( eccc.hpi-web.de/report/2013/026 ) A górna granica Udowodniono ciągu liczb zespolonych. Jest więc jakaś ogromna różnica w charakterystycznych polach zerowych i skończonych ...2O(n1/2logn)
Ryan Williams
Powinienem był wspomnieć o nowym wyniku. Czytałem artykuł i chciałem dowiedzieć się, co można wywnioskować ze znanych wyników dla przypadku pola skończonego. Zaktualizuje pytanie, aby uwzględnić artykuł.
Nikhil
Czy istnieją podobne / jakiekolwiek dolne granice znane dla wyznacznika / trwałe w przypadku obwodów o głębokości 3 ponad polami o charakterystyce zerowej?
Gorav Jindal
Powyżej charakterystycznego zera, AFAIK, najlepszą dolną granicą jest dla elementarnej funkcji symetrycznej (a także wyznacznika wielomianu) ze względu na Shpilkę i Wigdersona. Sprawdź cs.technion.ac.il/~shpilka/publications/…Ω(n2)
Nikhil

Odpowiedzi:

11

Stałe jest kompletne dla VNP w rzutach p na dowolnym polu nietypowym 2. To daje pozytywną odpowiedź na twoje drugie pytanie. Gdyby ta redukcja była liniowa, dałaby pozytywną odpowiedź na twoje pierwsze pytanie, ale uważam, że pozostaje otwarta.

Bardziej szczegółowo: istnieje pewien wielomian taki, że d e t n ( X ) jest rzutem p e r m q ( n ) ( Y ) , tzn. Istnieje pewna podstawienie wysyłające każdą zmienną y i j albo na zmienną x k lub stałą taką, że po tym podstawieniu q ( n ) × q ( n ) permanent oblicza nq(n)detn(X)permq(n)(Y)yijxkq(n)×q(n) wyznacznik.n×n

1) Tak więc wzór Rysera daje wzór na głębokość 3 (głębokość nie zwiększa się pod rzutami, ponieważ podstawienia można wykonać na bramkach wejściowych) o wielkości dla wyznacznika. AKTUALIZACJA : Jak wskazuje @Ramprasad w komentarzach, daje to coś nietrywialnego tylko wtedy, gdy q ( n ) = o ( n log n ) , ponieważ istnieje trywialna formuła głębokości 2 o wielkości n n ! = 2 O ( n log n )2O(q(n))q(n)=o(nlogn)nn!=2O(nlogn)dla det. Jestem z Ramprasad w tym, że najlepiej znam redukcję poprzez ABP, która daje .q(n)=O(n3)

2) Jeżeli stałą można obliczyć - ponownie na pewnym polu charakterystyki nie 2 - za pomocą obwodu o wielkości s ( m ) , to wyznacznik n × n można obliczyć za pomocą obwodu o wielkości s ( q ( n ) ) . Tak więc dolna granica b ( n ) na wielkości obwodu dla d e t n daje dolną granicę b ( q - 1 ( n ) ) na wielkości obwodu dla wartości stałej (to jestm×ms(m)n×ns(q(n))b(n)detnb(q1(n)) odwrotna, a nie 1 / q ( n ) ). Wyżej wymieniony q ( n ) = O ( N 3 ) daje b ( n 1 / 3 ), trwała ondulacja dolnej granicy z b ( n ) DET dolna granica.q 1/q(n)q(n)=O(n3)b(n1/3)b(n)

Joshua Grochow
źródło
6
Chciałbym tylko zaznaczyć, że wyznacznik będący rzutem wielomianowo większej stałej nie daje zbyt wiele. Wyznacznik ma oczywiście trywialne obwód wielkości. Zatem nawet wykazanie, że wyznacznik n × n jest rzutem stałej n 2 × n 2 , nie daje niczego nietrywialnego dzięki formule Rysera. Wydaje mi się, że dla twojej strategii dowodzenia trzeba pokazać, że q ( n ) = O ( n ) , ale nie widzę, jak to uzyskać ze zwykłej redukcji. AFAIK, brak obwodu o głębokości 3 asymptotycznie mniejszej niż n !n!n×nn2×n2q(n)=O(n)n!jest znany z wyznacznika ponad polami skończonymi.
Ramprasad
@Ramprasad: Istnieje rzut na P E R M O ( n ) w ogólnym przypadku na dowolnych polach, prawda? Więc wdrożenie tej redukcji na głębokości 3 jest przeszkodą - czy o to ci chodzi? DETnPERMO(n)
Nikhil
1
@Nikhil: Czy istnieje taka projekcja ?! Gdyby tak było, to oczywiście mielibyśmy natychmiast obwód głębokość-3 dla wyznacznika, po prostu stosując wzór Rysera (który nie był znany przed wynikiem otchłani na głębokości-3). Jedyną znaną mi redukcją jest wzięcie ABP dla wyznacznika (który ma rozmiar O ( n 3 ) ) i zapisanie tego jako rzutu stałej wielkości O ( n 3 ) . Byłbym bardzo zaskoczony redukcją stałych blokad o rozmiarze O ( n ) . 2O(n)O(n3)O(n3)O(n)
Ramprasad
1
Jestem całkiem pewien, że w tym artykule występuje literówka / błąd (ale sprawdzę z Manindrą). Przemówienie Aviego Wigdersona (PPT) podczas 60. urodzin Valiant jest jednym z miejsc, w których stwierdzono, że poprawa dla głębokości-3 złożoność wyznacznika była nieznana. Obwody głębokości-3 nad polami skończonymi to ciekawy przykład, w którym najlepsza górna granica dla wartości stałej jest mniejsza niż wyznacznik! n!
Ramprasad
1
niech nam kontynuować tę dyskusję w czacie
Ramprasad
11

Jest bardzo możliwe, że wyznacznik jest w pewnym sensie trudniejszy niż stały. Oba są wielomianami, Ranga Waringa (sumy n mocy form liniowych) stałej wynosi około 4 ^ n, Ranga Chow (suma iloczynów form liniowych) wynosi około 2 ^ n. Oczywiście Waring Rank \ leq 2 ^ {n-1} Ranga Chow. Dla wyznacznika liczby te są tylko dolnymi granicami. Z drugiej strony, jakiś czas temu udowodniłem, że ranga Waringa wyznacznika jest ograniczona przez (n + 1)! i to może być bliskie prawdy.

Leonid Gurvits
źródło
7
Usunąłem reklamę.
Jeffε
3
Czy możesz podać referencję dla dowodu?
Kaveh