The $K_{3,3}$ and cube running-time exponent conjecture

Let $K_{3,3}$ be the complete bipartite graph with parts of size three, let $Q_3$ be the three-dimensional cube graph, and let $M_H(n)$ denote the maximum running time of the $H$-process. Bipartite exponent conjecture.

$$M_{K_{3,3}}(n)=n^{3/2+o(1)}\qquad\text{and}\qquad M_{Q_3}(n)=n^{3/2+o(1)}.$$

Known lower bounds give exponent $3/2$ up to lower-order terms, while the best available upper bounds do not match them for these graphs. The conjecture asserts that the lower-bound exponent is essentially tight for both.