From Rick Kenyon's open problem list:
What are the minimal number of squares needed to tile an $a \times b$ rectangle?
Kenyon showed the correct order is $\log a$ assuming $a/b$ is bounded with $b \leq a$. However, there is plenty of room for improvement in the constant factor, and an exact formula seems far, far away.
