Which problems in computational geometry or graph theory are believed to be $\Omega(n^3)$?
Posted by Bob Fraser, at cstheory.stackexchange.com,
This is intended as a follow up question to Robin Kothari's previous post on polynomial time hardness results. Specifically, I'm…