In a paper by Raphael Pass, he writes (page 162):
... most natural problems that we believe are hard on average for polynomial time are also believed hard for quasi-polynomial time.
In another post by Turkistany, he mentioned that the log-CLIQUE problem is solvable in quasi-polynomial time.
What are some other natural problems which we believe are hard on average for polynomial time, but can be decided/solved in quasi-polynomial time?
