¿Qué problemas en geometría computacional o teoría de grafos se cree que son ?

Esto pretende ser una pregunta de seguimiento a la publicación anterior de Robin Kothari sobre los resultados de la dureza del tiempo polinomial .

Específicamente, estoy interesado en ver algunas pruebas de dureza para problemas que se cree que tienen límites inferiores aproximadamente , y digo aproximadamente para permitir mejoras ligeramente subcúbicas jugando con el tamaño de palabra (como el de 3SUM por Barab et al. [A través de Springer] ). Me encantaría mantener los problemas en el modelo de árbol de decisión si simplifica las respuestas.$\Omega(n^3)$

Desde el puesto de Robin, he aprendido acerca de Jeff Erikson papel que da una límite inferior para 5SUM (más exactamente, muestra que carreras -sum en tiempo en general).$\Omega(n^3)$$k$$\Omega (n^{\lceil k/2 \rceil})$

¿Existen documentos u otras referencias que usen tales reducciones para conjeturar límites cúbicos inferiores para problemas de geometría computacional o teoría de grafos?

Creo que el documento " Equivalencias subcúbicas entre problemas de trayectoria, matriz y triángulo " de V. Vassilevska Williams y R. Williams es lo que está buscando. Su resumen contiene la lista de los siguientes problemas en gráficos:

• El problema de los caminos más cortos de todos los pares en los dígrafos ponderados (APSP).
• Detectar si un gráfico ponderado tiene un triángulo de peso de borde total negativo.
• Enumerar hasta triángulos negativos en un gráfico ponderado por el borde.$n^{2.99}$
• El problema de las rutas de reemplazo en los dígrafos ponderados.
• Encontrar la segunda ruta simple más corta entre dos nodos en un dígrafo ponderado.

Según el resumen, el documento trata sobre lo siguiente:

Definimos una noción de reducibilidad subcúbica y mostramos que muchos problemas importantes en gráficos y matrices que se pueden resolver en el tiempo son equivalentes en reducciones subcúbicas.$O(n^3)$

Entonces se pueden usar reducciones a estos problemas como punto de partida para probar los límites inferiores. Consulte, por ejemplo, la sección 5 en el siguiente documento: http://valis.cs.uiuc.edu/~sariel/papers/03/lms/lms.pdf . También las secciones 4 y 5 en el siguiente documento: http://valis.cs.uiuc.edu/~sariel/papers/08/expand_cover/expand_cover.pdf . Estoy seguro de que hay otros ejemplos: estos son solo documentos en los que trabajé y recuerdan que usan tal argumentación.

Por ejemplo, lo anterior demuestra que dado un conjunto de medios espacios ponderados en , encontrar la cobertura de peso mínimo de en estos medios espacios requiere tiempo de .ℜ 5 Ω ( n 5$\Re^5$$\Re^5$$\Omega(n^5)$