Recientemente ha habido algunos resultados nuevos en el estudio experimental basado en computadora del Problema de Discrepancia de Erdos (EDP) (a través de solucionadores SAT, citados a continuación). Este problema ha sido citado y estudiado por varios investigadores de (T) CS. Sin embargo, los enlaces (¿posiblemente profundos?) A (T) CS no son tan obvios.
¿Cuáles son los enlaces del EDP a (T) CS?
Aquí hay algunas referencias que muestran interés de la comunidad (T) CS en EDP:
Ataque SAT a EDP por Konev y Lisitsa, y reacción de Gowers ; también, otras conexiones a TCS empírico / experimental (por ejemplo, pruebas de teorema automatizadas SAT)
Introducción a EDP y técnicas en el blog de Lipton
EDP y privacidad diferencial en el blog Windows on Theory, de Talwar
Proyecto de polímosis EDP , con algunas contribuciones de informáticos
Respuestas:
Hay muchos vínculos entre la teoría de la discrepancia y la informática, y Bernard Chazelle ha examinado bellamente algunos de ellos en su libro . También se han encontrado varios enlaces más recientemente, por ejemplo, la publicación de blog de Kunal habla sobre la conexión a la privacidad diferencial de [MN] y [NTZ] . Otro ejemplo es la idea de Larsen de utilizar la discrepancia para probar los límites inferiores del tiempo de actualización / consulta para las estructuras de datos dinámicos. Muchos de estos enlaces se pueden instanciar con progresiones aritméticas homogéneas (HAP). Esto daría:
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 distribución de HAP sean muy naturales. ¿Cuándo espera tener una entrada que sea un conjunto múltiple de enteros y desea responder cuántos elementos de un HAP hay en la entrada? No puedo pensar en una situación cuando esto surge, pero tal vez me estoy perdiendo algo.
Otra cosa que debe 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: hay límites inferiores más fuertes disponibles para ella, es aproximable a factores pollogarí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.juntos esencialmente resuelven la discrepancia hereditaria de los HAP. Como explica Kunal, la intuición para el 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 anteriores 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 cual EDP aún está abierto, mientras que la pregunta de discrepancia hereditaria se entiende bastante bien.
Permítanme terminar con un enfoque para atacar EDP que está inspirado en ideas informáticas. Hay una manera de relajar la discrepancia con un programa semidefinido; consulte la encuesta de Bansal para obtener más detalles. El valor óptimo del programa semidefinido está limitado por el valor de cualquier solución factible para su programa dual. Por lo tanto, uno puede intentar probar EDP exhibiendo una familia de soluciones duales a esta relajación semidefinida de discrepancia, y mostrando que el valor de las soluciones duales es infinito. No veo ninguna razón por la cual tal ataque no pueda funcionar, en particular, no sabemos cómo construir soluciones a la relajación semidefinida que tengan un valor constante para instancias arbitrariamente grandes. De hecho, gran parte del esfuerzo en polymath5 se centró en encontrar o descartar soluciones duales con una estructura particular.
fuente