Mi pregunta es ¿por qué los límites inferiores para los circuitos booleanos de profundidad 3 con puertas "y" y "xor" para determinante no implican los mismos límites inferiores para los circuitos aritméticos sobre ?ZZ\mathbb{Z} Lo que está mal con el siguiente argumento: Sea un determinante...
Sea un polinomio dado por un circuito aritmético C de tamaño s . Dado C como entrada, ¿existe un algoritmo determinista para verificar si todos los factores irreducibles de f en Q [ x 1 , x 2 , ... , x n ] son formas lineales? En una nota relacionada, dada una forma lineal l = ∑ n i...
Sea un polinomio variable dado como un circuito aritmético de tamaño poly , y sea un primo.Fffnortenn( n )(n)(n)p = 2Ω ( n )p=2Ω(n)p = 2^{\Omega(n)} ¿Puede probar si es idénticamente cero sobre , con tiempo y probabilidad de error , incluso si el grado no es a priori acotado? ¿Qué pasa si es...
El algoritmo de Berkowitz proporciona un circuito de tamaño polinómico con profundidad logarítmica para determinar una matriz cuadrada utilizando potencias matriciales. El algoritmo utiliza implícitamente la cancelación. ¿Es esencial la cancelación para lograr un circuito de tamaño polinómico con...
Este resultado de Tavenas, Koiran y otros muestran que cualquier polinomio calculado por un circuito de tamaño sss se calcula por un circuito homogéneo de profundidad 4 de tamaño sd√sds^{\sqrt{d}} . ¿Hay resultados similares para los circuitos booleanos o sabemos por qué tal cosa no es posible?...
¿Existe una prueba alternativa o una exposición del resultado de Grigoriev y Karpinski (STOC 1998, doi: 10.1145 / 276698.276872 ) en los límites inferiores exponenciales para circuitos aritméticos de Profundidad 3 que calculan sobre un campo finito fijo?DETn×nDETn×n\mathsf{DET}_{n\times n} No pude...