Grado aproximado de

24

EDITAR (v2): se agregó una sección al final sobre lo que sé sobre el problema.

EDITAR (v3): discusión agregada sobre el grado de umbral al final.

Pregunta

Esta pregunta es principalmente una solicitud de referencia. No sé mucho sobre el problema. Quiero saber si ha habido trabajo previo sobre este problema, y ​​si es así, ¿alguien puede señalarme algún documento que hable sobre este problema? También me gustaría conocer los mejores límites actuales en el grado aproximado de . Cualquier otra información también sería apreciada (por ejemplo, información histórica, motivación, relación con otros problemas, etc.).AC0

Definiciones

Deje que sea ​​una función booleana. Sea un polinomio sobre las variables a con coeficientes reales. El grado de un polinomio es el grado máximo sobre todos los monomios. El grado de un monomio es la suma de exponentes de los diversos que aparecen en ese monomio. Por ejemplo .f:{0,1}n{0,1}px1xnxideg(x17x32)=9

Se dice que un polinomio -aproximadamente if para todas las . El grado aproximado de una función booleana , denotado como , es el grado mínimo de un polinomio que -aproxima a . Para un conjunto de funciones, , es el grado mínimo modo que cada función en puede ser aproximada por un polinomio de grado como máximopϵf|f(x)p(x)|<ϵxϵfdeg~ϵ(f)f F ~ deg ϵ ( F ) d F ϵ dϵfFdeg~ϵ(F)dFϵd.

Tenga en cuenta que cada función se puede representar sin error por un polinomio de grado . Algunas funciones realmente necesitan un polinomio de grado para aproximarse a cualquier error constante. La paridad es un ejemplo de tal función.nn

Planteamiento del problema

¿Qué es ? (La constante 1/3 es arbitraria).deg~1/3(AC0)

Notas

Encontré este problema en el artículo The Quantum Query Complexity of AC0 de Paul Beame y Widad Machmouchi. Ellos dicen

Además, nuestros resultados no hacen nada para cerrar la brecha en el límite inferior en el grado aproximado de las funciones AC0.

Mencionan "el problema del grado aproximado de AC0" en sus agradecimientos también.

¿Entonces supongo que ha habido algún trabajo sobre este problema antes? ¿Alguien puede señalarme un artículo que habla sobre el problema? ¿Y cuáles son los límites superior e inferior más conocidos?

Lo que sé sobre el problema (esta sección se agregó en la v2 de la pregunta)

El límite superior más conocido en que se conoce es el límite superior trivial . El mejor límite inferior que conozco proviene del límite inferior de Aaronson y Shi para los problemas de colisión y distinción de elementos, lo que da un límite inferior de . (Para versiones severamente restringidas de , como fórmulas con tamaño de fórmula , o circuitos de profundidad-2 con compuertas , podemos probar un límite superior utilizando la complejidad de la consulta cuántica).n ~ Ω (n2/3)AC0o(n2)O(n2)o(n)deg~1/3(AC0)nΩ~(n2/3)AC0o(n2)o(n2)o(n)

Relacionado: grado umbral (agregado en v3)

Como Tsuyoshi señala en los comentarios, este problema está relacionado con el problema de determinar el grado umbral de . El grado de umbral de una función es el grado mínimo de un polinomio tal que y . fpf(x)=1AC0fpf ( x ) = 0f(x)=1p(x)>0f(x)=0p(x)<0

Sherstov ahora ha mejorado los límites inferiores para el grado umbral de . Exhibe una familia de fórmulas de lectura única de profundidad constante en variables cuyo grado de umbral se aproxima a medida que la profundidad llega al infinito, lo cual es casi estricto ya que las fórmulas de lectura única tienen umbral (e incluso aproximado ) grado . Ver http://eccc.hpi-web.de/report/2014/009/ . (Enero de 2014) nΩ(AC0nO(Ω(n)O(n)

Robin Kothari
fuente
77
Se conoce un límite inferior Ω (n ^ (1/3)) incluso para el grado umbral (el grado mínimo de un polinomio p tal que f (x) = 1 ⇒ p (x)> 0 yf (x) = 0 ⇒ p (x) <0). Consulte el final de la Sección 3.1 de "Límites inferiores de comunicación utilizando polinomios duales" de Sherstov .
Tsuyoshi Ito
44
@ Tsuyoshi: Gracias. El grado de umbral (que limita el grado aproximado) de AC0 también es una pregunta interesante. Los mejores límites inferiores que conozco para el grado de umbral de AC0 están en Nuevos límites de grado para las funciones de umbral polinomiales de O'Donnell y Servedio. El límite inferior es mejor que Ω (n ^ (1/3)) por un factor logarítmico que crece con la profundidad del circuito.
Robin Kothari
44
Vaya, tienes razón, el límite inferior en el grado de aproximación para AC0 es obvio por Aaronson y Shi. Tonto de mí. Gracias por el puntero a O'Donnell y Servedio, también. Ω~(n2/3)
Tsuyoshi Ito
Un artículo reciente de Mark Bun y Justin Thaler titulado "Amplificación de la dureza y el grado aproximado de los circuitos de profundidad constante" también analiza brevemente este problema. Dicen que el límite inferior de Aaronson y Shi es el límite inferior más conocido para una función en AC <sup> 0 </sup> y ese límite inferior incluso se cumple en un modelo un poco más general.
Robin Kothari

Respuestas:

4

Recientemente se publicó un artículo de Mark Bun y Justin Thaler en ECCC (mediados de marzo de 2017) que responde con precisión a esta pregunta: "Un límite inferior casi óptimo en el grado aproximado de AC0"

Afirman que para cualquier , existe una función en tal que , casi cerrando la brecha con el límite superior trivial . Lo logran con un método general para aumentar el grado aproximado de una función con un grado aproximado sublineal, manteniendo el número de variables cuasi-lineales. Del resumen:f A C 0 ~ d e g 1 / 3 ( f ) = Ω ( n 1 - δ ) O ( n )δ>0fAC0deg~1/3(f)=Ω(n1δ)O(n)

Específicamente, mostramos cómo transformar cualquier función booleana con un grado aproximado en una función en las variables con un grado aproximado al menos . En particular, si , entonces es polinomialmente más grande que . Por otra parte, si se calcula por una de tamaño polinomio circuito booleano de profundidad constante, entonces también lo es .d F O ( n p o l y l o g ( n ) ) D = Ω ( n 1 / 3 · d 2 / 3 ) d = n 1 - Ω ( 1 ) D d f FfdFO(npolylog(n))D=Ω(n1/3·d2/3)d=n1Ω(1)DdfF

Esa es la actualización más reciente en el límite inferior de este problema, y ​​es un avance bastante significativo. Las secciones de Introducción y Aplicación del documento también son buenas fuentes de referencias para trabajos anteriores y problemas relacionados.

Descargo de responsabilidad: no he leído el periódico con cuidado todavía.

UN
fuente
De hecho, esto casi cierra el problema. También muestran un DNF de tamaño cuasipolinomial con grado aproximado . Ω(n1δ)
Robin Kothari