reference-request – ¿Conexiones entre el problema de la discrepancia de Erdos y la CS (teórica)?

Pregunta:

Recientemente, ha habido algunos resultados nuevos en un estudio experimental basado en computadora del problema de discrepancia de Erdos (EDP) (a través de solucionadores SAT, que se citan a continuación). Este problema ha sido citado y estudiado por varios investigadores de (T) CS. Sin embargo, los vínculos (¿posiblemente profundos?) Con (T) CS no son tan obvios.

¿Cuáles son los enlaces del EDP a (T) CS?

Aquí hay algunas referencias que muestran el interés de la comunidad (T) CS en EDP:

Respuesta:

Hay muchos vínculos entre la teoría de la discrepancia y la informática, y Bernard Chazelle ha examinado maravillosamente algunos de ellos en su libro . También se han encontrado varios enlaces más recientemente, por ejemplo, la publicación del blog de Kunal habla sobre la conexión con la privacidad diferencial de [MN] y [NTZ] . Otro ejemplo es la idea de Larsen de usar la discrepancia para probar los límites inferiores del tiempo de actualización / consulta para estructuras de datos dinámicas. Muchos de estos enlaces se pueden instanciar con progresiones aritméticas homogéneas (HAP). Esto daría:

  • límites superiores en $ \ varepsilon $ -muestras para espacios de rango de HAP
  • límites inferiores en el tiempo requerido para actualizar / consultar una estructura de datos dinámica para el recuento de rango HAP
  • límites inferior y superior en el error requerido para responder de forma privada las consultas HAP

Sin embargo, hay dos cosas que debe tener en cuenta con respecto a estos enlaces. Una es que no está claro que los espacios de rango de los HAP sean muy naturales. ¿Cuándo espera tener una entrada que sea un conjunto múltiple de números enteros y desea responder cuántos elementos de un HAP hay en la entrada? No puedo pensar en una situación en la que esto surja, pero tal vez me esté perdiendo algo.

Otra cosa que debes tener en cuenta es que todas estas aplicaciones se basan en la noción de discrepancia hereditaria . Esta noción es más robusta que la discrepancia, lo que la hace más manejable: existen límites inferiores más fuertes disponibles para ella, es aproximable dentro de factores polilogarítmicos y es aproximadamente igual al valor de un problema de optimización convexa. El resultado del que habla Kunal en la publicación del blog (el artículo está aquí ) y la construcción de Alon y Kalai sobre la que Kalai escribió en esta publicación del blog, esencialmente resuelven la discrepancia hereditaria de los HAP. Como explica Kunal, la intuición del límite inferior de la discrepancia hereditaria de los HAP provino de la estrecha conexión entre la discrepancia hereditaria y la privacidad diferencial, junto con los resultados previos en la privacidad diferencial.

Sin embargo, EDP se trata de la discrepancia de los HAP. La discrepancia es mucho más frágil que la discrepancia hereditaria, y eso hace que sea más difícil reducir el límite. Esto también lo hace menos útil en aplicaciones que la discrepancia hereditaria. Y esta es la razón por la que la EDP sigue abierta, mientras que la cuestión de la discrepancia hereditaria se comprende bastante bien.

Permítanme terminar con un enfoque para atacar EDP que está inspirado en ideas de ciencias de la computación. Hay una manera de relajar la discrepancia con un programa semidefinito; consulte la encuesta de Bansal para obtener más detalles. El valor óptimo del programa semidefinito está limitado más bajo por el valor de cualquier solución factible para su programa dual. Por lo tanto, se puede intentar probar EDP exhibiendo una familia de soluciones duales para esta relajación semidefinida de discrepancia, y mostrando que el valor de las soluciones duales llega al infinito. No veo ninguna razón por la que tal ataque no pueda funcionar, en particular, no sabemos cómo construir soluciones para la relajación semidefinida que tengan un valor constante para instancias arbitrariamente grandes. De hecho, gran parte del esfuerzo de Polymath5 se centró en encontrar o descartar soluciones duales con una estructura particular.

La discrepancia de progresiones aritméticas arbitrarias es $ \ Theta (n ^ {1/4}) $ en el peor de los casos: el límite inferior se conoce como el teorema 1/4 de Roth. Lovasz da una prueba del teorema usando programación semidefinida (aunque argumentando directamente sobre el primario en lugar de construir soluciones duales). Para la prueba, consulte la Sección 5.2. de su encuesta SDP .

Leave a Comment

Your email address will not be published.

Scroll to Top

istanbul avukat

-

web tasarım