Following a suggestion of Jordan Ellenberg, we study measures of complexity for self-correspondences of some classes of varieties. We also answer a question of Rhyd concerning curves sitting in the square of a very general hyperelliptic curve.