Masalah apa dalam geometri komputasi atau teori grafik yang diyakini

Ini dimaksudkan sebagai pertanyaan lanjutan terhadap pos Robin Kothari sebelumnya tentang hasil kekerasan waktu polinomial .

Secara khusus, saya tertarik melihat beberapa bukti kekerasan untuk masalah yang diyakini memiliki kira-kira batas bawah, dan saya katakan secara kasar untuk memungkinkan perbaikan sedikit subkubis dengan bermain dengan ukuran kata (seperti untuk 3SUM oleh Barab et al. [Melalui Springer] ). Saya akan senang menyimpan masalah dalam model pohon keputusan jika menyederhanakan tanggapan.$\Omega(n^3)$

Dari pos Robin, saya belajar tentang makalah Jeff Erikson yang memberikan batas bawah untuk 5SUM (lebih akurat, ia menunjukkan bahwa k -SUM berjalan pada Ω ( n ⌈ k / 2 ⌉ ) waktu secara umum).$\Omega(n^3)$$k$$\Omega (n^{\lceil k/2 \rceil})$

Apakah ada makalah atau referensi lain yang menggunakan reduksi seperti itu untuk menduga batas bawah kubik untuk masalah dalam geometri komputasi atau teori grafik?

Saya pikir makalah " Persamaan Subkubis Antara Masalah Jalur, Matriks, dan Segitiga " oleh V. Vassilevska Williams dan R. Williams adalah yang Anda cari. Abstraknya berisi daftar masalah berikut pada grafik:

• Masalah jalur terpendek semua-pasangan pada digraph tertimbang (APSP).
• Mendeteksi jika grafik berbobot memiliki segitiga dengan bobot tepi total negatif.
• $n^{2.99}$
• Masalah jalur penggantian pada digraf tertimbang.
• Menemukan jalur sederhana terpendek kedua antara dua node dalam digraf tertimbang.

Menurut abstrak, makalah ini membahas hal-hal berikut:

$O(n^3)$

Satu kemudian dapat menggunakan pengurangan untuk masalah ini sebagai titik awal untuk membuktikan batas bawah. Lihat misalnya bagian 5 dalam makalah berikut: http://valis.cs.uiuc.edu/~sariel/papers/03/lms/lms.pdf . Juga bagian 4 dan 5 dalam makalah berikut: http://valis.cs.uiuc.edu/~sariel/papers/08/expand_cover/expand_cover.pdf . Saya yakin ada contoh lain - ini hanya makalah yang saya kerjakan dan ingat mereka menggunakan argumen seperti itu.

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