Que problemas na geometria computacional ou teoria gráfico são acreditados para ser

Isso pretende ser uma pergunta de acompanhamento do post anterior de Robin Kothari sobre resultados de dureza do tempo polinomial .

Especificamente, estou interessado em ver algumas provas de dureza para problemas que se acredita terem limites mais baixos, e digo aproximadamente para permitir melhorias ligeiramente sub-cúbicas ao brincar com o tamanho da palavra (como o de 3SUM by Barab et al. [Via Springer] ). Eu ficaria feliz em manter os problemas no modelo de árvore de decisão se simplificasse as respostas.$\Omega(n^3)$

Desde o post de Robin, eu aprendi sobre Jeff Erikson papel que dá uma limite inferior para 5SUM (mais precisamente, ele mostra que k -sum é executado em Ω ( n ⌈ k / 2 ⌉ ) de tempo em geral).$\Omega(n^3)$$k$$\Omega (n^{\lceil k/2 \rceil})$

Existem documentos ou outras referências usando essas reduções para conjecturar limites inferiores cúbicos para problemas em geometria computacional ou teoria de grafos?

Acho que o artigo " Equivalências subcúbicas entre problemas de caminho, matriz e triângulo " de V. Vassilevska Williams e R. Williams é o que você está procurando. Seu resumo contém a lista dos seguintes problemas nos gráficos:

• O problema dos caminhos mais curtos de todos os pares nos dígrafos ponderados (APSP).
• Detectando se um gráfico ponderado possui um triângulo com o peso total negativo da aresta.
• Listando até triângulos negativos em um gráfico ponderado pela aresta.$n^{2.99}$
• O problema dos caminhos de substituição nos dígrafos ponderados.
• Localizando o segundo caminho simples mais curto entre dois nós em um dígrafo ponderado.

De acordo com o resumo, o artigo é sobre o seguinte:

Definimos uma noção de redutibilidade subcúbica e mostramos que muitos problemas importantes em gráficos e matrizes solucionáveis ​​no tempo de são equivalentes nas reduções subcúbicas.$O(n^3)$

Pode-se então usar reduções para esse problema como ponto de partida para provar limites mais baixos. Veja, por exemplo, a seção 5 no seguinte documento: http://valis.cs.uiuc.edu/~sariel/papers/03/lms/lms.pdf . Também as seções 4 e 5 do documento a seguir: http://valis.cs.uiuc.edu/~sariel/papers/08/expand_cover/expand_cover.pdf . Tenho certeza de que existem outros exemplos - são apenas os trabalhos em que trabalhei e esses lembram que usam essa argumentação.

$\Re^5$$\Re^5$$\Omega(n^5)$