Limite inferior para determinante e permanente

22

À luz do resultado recente do abismo na profundidade 3 (que, entre outras coisas, produz profundidade-3 circuito aritmético para onxndeterminante sobreC), que têm as seguintes questões: Grigoriev e Karpinskirevelouum2Ω(n)um limite inferior para qualquer profundidade-3 circuito aritmético de computação o determinante denxnmatrizes sobre campos finitos (o que eu acho, também vale para o Permanente). A fórmula de Ryserpara calcular o Permanent fornece um circuito aritmético de profundidade 3 do tamanhoO(n22n)=2O(2nlognn×nC2Ω(n)n×n . Isso mostra que o resultado é essencialmente rígido para os circuitos de profundidade 3 para os campos permanentes sobre finitos. Eu tenho duas perguntas:O(n22n)=2O(n)

1) Existe uma fórmula de profundidade 3 para o determinante análogo à fórmula de Ryser para o Permanente?

2) Um limite inferior no tamanho dos circuitos aritméticos que calculam o polinômio determinante \ textit {sempre} gera um limite inferior para o polinômio Permanente? (Acima de eles são os mesmos polinômios).F2

Embora minha pergunta atual seja sobre esses polinômios em campos finitos, eu também gostaria de saber o status dessas perguntas em campos arbitrários.

Nikhil
fonte
3
Isso é interessante .... recentemente ( eccc.hpi-web.de/report/2013/026 ) a limite superior foi provado sobre os números complexos. Portanto, não é de alguma forma uma enorme diferença em campos de zero e finitos característicos ...2O(n1/2logn)
Ryan Williams
Eu deveria ter mencionado o novo resultado. Eu estava lendo o jornal e queria saber o que pode ser inferido a partir de resultados conhecidos para o caso de campo finito. Atualizará a pergunta para incluir o artigo.
Nikhil
Existem limites similares / inferiores conhecidos como determinantes / permanentes no caso de circuitos de profundidade 3 sobre campos da característica zero?
Gorav Jindal
Acima da característica zero, AFAIK, o melhor limite inferior é Ω(n2) para a função simétrica elementar (e também o polinômio determinante) devido a Shpilka e Wigderson. Verifique cs.technion.ac.il/~shpilka/publications/…
Nikhil

Respostas:

11

O Permanent é completo para o VNP sob projeções p sobre qualquer campo não da característica 2. Isso fornece uma resposta positiva para sua segunda pergunta. Se essa redução fosse linear, daria uma resposta positiva à sua primeira pergunta, mas acredito que isso permanece em aberto.

Em mais pormenor: há alguns polinómio de tal modo que d e t n ( X ) é uma projecção de p e r m q ( n ) ( Y ) , ou seja, há um certo substituição envio de cada variável y i j tanto a uma variável x k ou a uma constante tal que após essa substituição a permanente q ( n ) × q ( n ) esteja computando nq(n)detn(X)permq(n)(Y)yijxkq(n)×q(n) determinante.n×n

1) Assim, a fórmula de Ryser produz uma fórmula de profundidade 3 (a profundidade não aumenta sob as projeções, porque as substituições podem ser feitas nas portas de entrada) do tamanho para determinante. ATUALIZAÇÃO : Como @Ramprasad aponta nos comentários, isso só fornece algo não trivial se q ( n ) = o ( n log n ) , pois existe uma fórmula trivial de profundidade 2 do tamanho n n ! = 2 O ( n log n )2O(q(n))q(n)=o(nlogn)nn!=2O(nlogn) para det. Estou com Ramprasad, pois o melhor que conheço é a redução através de ABPs, o que gera .q(n)=O(n3)

2) Se a permanente pode ser calculada - novamente, sobre algum campo de característica não 2 - por um circuito do tamanho s ( m ) , então n × n determinante pode ser calculado por um circuito do tamanho s ( q ( n ) ) . Portanto, um limite inferior de b ( n ) no tamanho do circuito para d e t n produz um limite inferior de b ( q - 1 ( n ) ) no tamanho do circuito para o permanente (isto ém×ms(m)n×ns(q(n))b(n)detnb(q1(n)) inverso, não 1 / q ( nq ). O acima mencionado q ( n ) = O ( n 3 ) produz um b ( n 1 / 3 ) perm limite inferior de uma b ( n ) Det limite inferior.1/q(n)q(n)=O(n3)b(n1/3)b(n)

Joshua Grochow
fonte
6
Só quero salientar que o determinante é uma projeção de uma permanente polinomialmente maior não produz muito. O determinante, é claro, tem um trivial ! circuito de tamanho. Assim, mesmo mostrando que o n x n determinante é uma projecção de um n 2 × n 2 permanente não deu nada não trivial através da fórmula Ryser. Eu acho que, para sua estratégia de prova, é preciso mostrar que q ( n ) = O ( n ) , mas não vejo como obter isso da redução usual. AFAIK, nenhum circuito de profundidade 3 assintoticamente menor que n !n!n×nn2×n2q(n)=O(n)n! is known for the determinant over finite fields.
Ramprasad
DETnPERMO(n) in the general case over arbitrary fields right? So implementing this reduction in depth-3 is the hurdle - is that what you mean?
Nikhil
1
@Nikhil: Is there such a projection?! If that were true, then of course we would immediately have a 2O(n) depth-3 circuit for the determinant by just using Ryser's formula (which wasn't known prior to the chasm-at-depth-3 result). The only reduction I know is to take the ABP for the determinant (whcih is O(n3)-sized) and write that as a projection of a O(n3) sized permanent. I would be very surprised of a reduction to O(n)-sized permanent holds.
Ramprasad
1
I'm fairly sure that is a typo/error in the article (but I shall check with Manindra though). Avi Wigderson's talk (PPT) during Valiant's 60th birthday celebrations is one of the places where it was stated that improving n! for the depth-3 complexity of determinant was unknown. Depth-3 circuits over finite fields is a curious example where the best upper bound for the permanent is smaller than the determinant!
Ramprasad
11

It is very possible that the determinant is, in a way, harder than the permanent. They are both polynomials, the Waring Rank(sums of n powers of linear forms) of the permanent is roughly 4^n, Chow Rank(sums of products of linear forms) is roughly 2^n. Clearly, Waring Rank \leq 2^{n-1} Chow Rank. For the determinant, those numbers are just lower bounds. On the other hand, I proved a while ago that the Waring rank of the determinant is upper bounded by (n+1)! and this might be close to the truth.

Leonid Gurvits
fonte
7
I removed the advertisement.
Jeffε
3
Can you give the reference for the proof?
Kaveh