Which paper? Is it this? https://link.springer.com/article/10.1007/BF00941892 I'm willing to give it a shot but that abstract doesn't scream "easy to read" to me.

What's an epsilon-ball? I'm guessing it somehow describes the resolution you need to sample at in order to guarantee you've found all the local maximums? I guess what I'm struggling with is that, with a probabilistic search through a space you don't already know the properties of, I don't see how that can be anything other than checking every solution in turn - in other words a brute force search.

Does this all boil down to "the worse-case scenario of simulated annealing is brute force search"? And where does the logarithmic cooling schedule come in?