Jakie problemy w geometrii obliczeniowej lub teorii grafów uważa się za

Jest to pytanie uzupełniające do poprzedniego postu Robina Kothari na temat wyników twardości wielomianowej .

Interesuje mnie w szczególności sprawdzenie niektórych dowodów twardości dla problemów, które mają z grubsza dolne granice, i mówię z grubsza, aby pozwolić na nieco subkubiczne ulepszenia, grając z rozmiarem słowa (np. 3SUM autorstwa Barab i wsp. [Przez Springera] ). Z przyjemnością utrzymam problemy w modelu drzewa decyzyjnego, jeśli uprości to odpowiedzi.$\Omega(n^3)$

Z postu Robina dowiedziałem się o artykule Jeffa Eriksona, który podaje dolną granicę dla 5SUM (dokładniej pokazuje, że SUM działa w czas w ogóle).$\Omega(n^3)$$k$$\Omega (n^{\lceil k/2 \rceil})$

Czy istnieją papiery lub inne odnośniki wykorzystujące takie redukcje do przypuszczenia sześciennych dolnych granic dla problemów w geometrii obliczeniowej lub teorii grafów?

Myślę, że artykuł pod tytułem „ Podkubiczne równoważności problemów ścieżki, macierzy i trójkąta ” autorstwa V. Vassilevskiej Williams i R. Williamsa jest tym, czego szukasz. Jego streszczenie zawiera listę następujących problemów na wykresach:

• Problem wszystkich par najkrótszych ścieżek na ważonych digrafach (APSP).
• Wykrywanie, czy wykres ważony ma trójkąt o ujemnej całkowitej masie krawędzi.
• Lista do trójkątów ujemnych na wykresie ważonym na krawędzi.$n^{2.99}$
• Problem ścieżek zastępczych na ważonych digrafach.
• Znalezienie drugiej najkrótszej prostej ścieżki między dwoma węzłami w ważonym digrafie.

Według streszczenia artykuł dotyczy następujących zagadnień:

Definiujemy pojęcie subkubicznej redukowalności i pokazujemy, że wiele ważnych problemów na wykresach i macierzach możliwych do rozwiązania w czasie jest równoważnych w ramach redukcji subkubicznych.$O(n^3)$

Następnie można użyć redukcji tego problemu jako punktu wyjścia do udowodnienia dolnych granic. Patrz na przykład sekcja 5 w następującym dokumencie: http://valis.cs.uiuc.edu/~sariel/papers/03/lms/lms.pdf . Również sekcja 4 i 5 w następującym dokumencie: http://valis.cs.uiuc.edu/~sariel/papers/08/expand_cover/expand_cover.pdf . Jestem pewien, że istnieją inne przykłady - to tylko dokumenty, nad którymi pracowałem i tacy pamiętają, że używają takiej argumentacji.

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