Quels problèmes en géométrie numérique ou en théorie des graphes seraient

Ceci est destiné à être une question complémentaire au précédent article de Robin Kothari sur les résultats de la dureté polynomiale .

Plus précisément, je suis intéressé à voir des preuves de dureté pour des problèmes qui sont censés avoir environ des limites inférieures, et je dis à peu près pour permettre des améliorations légèrement subcubiques en jouant avec la taille du mot (comme celle de 3SUM par Barab et al. [Via Springer] ). Je serais heureux de garder les problèmes dans le modèle d'arbre de décision s'il simplifie les réponses.$\Omega(n^3)$

Du poste de Robin, j'ai appris Jeff Erikson document qui donne un inférieure à destination de 5SUM ( avec plus de précision, il montre que k exécute -sum dans Ω ( n ⌈ k / 2 ⌉ ) de temps en général).$\Omega(n^3)$$k$$\Omega (n^{\lceil k/2 \rceil})$

Existe-t-il des articles ou d'autres références utilisant de telles réductions pour conjecturer des bornes inférieures cubiques pour des problèmes de géométrie informatique ou de théorie des graphes?

Je pense que l'article " Équivalences subcubiques entre les problèmes de chemin, de matrice et de triangle " de V. Vassilevska Williams et R. Williams est ce que vous recherchez. Son résumé contient la liste des problèmes suivants sur les graphiques:

• Le problème des chemins les plus courts toutes paires sur les digraphes pondérés (APSP).
• Détecter si un graphique pondéré a un triangle de poids total de bord négatif.
• $n^{2.99}$
• Le problème des chemins de remplacement sur les digraphes pondérés.
• Recherche du deuxième chemin simple le plus court entre deux nœuds dans un digraphe pondéré.

Selon le résumé, l'article porte sur les points suivants:

$O(n^3)$

On peut alors utiliser des réductions de ces problèmes comme point de départ pour prouver des limites inférieures. Voir par exemple la section 5 dans le document suivant: http://valis.cs.uiuc.edu/~sariel/papers/03/lms/lms.pdf . Voir également les sections 4 et 5 de l'article suivant: http://valis.cs.uiuc.edu/~sariel/papers/08/expand_cover/expand_cover.pdf . Je suis sûr qu'il y a d'autres exemples - ce ne sont que des papiers sur lesquels j'ai travaillé et ceux-là se souviennent qu'ils utilisent une telle argumentation.

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