  The Nisan-Ronen conjecture states that no truthful mechanism for
makespan-minimization when allocating $m$ tasks to $n$ unrelated machines can
have approximation ratio less than $n$. Over more than two decades since its
formulation, little progress has been made in resolving it and the best known
lower bound is still a small constant. This work makes progress towards
validating the conjecture by showing a lower bound of $1+\sqrt{n-1}$.
