Define L = (a+b)/2 and R = (a-b)/2, so that a * b = L² - R² for all a, b.
If there exist positive integers a, b such that a * b = n with |a-b| <= k n^(1/4) [constant k]
Then there exist L, R (either both integers or both half-integers) with L² - R² = n and |R| <= (1/2) k n^(1/4)
From which one can deduce:
R² <= (k²/4) √n
L² - R² >= L² - (k²/4) √n
n >= L² - (k²/4) √n
L² <= n + (k²/4) √n
L <= √(n + (k²/4) √n)
L <= √n + k²/8
If k <= 1, then L must be ceil(√n) or ceil(√n) - 1/2
If k <= 2√2, then L must be ceil(√n), ceil(√n) - 1/2, or ceil(√n) + 1/2
(my original estimate of 2 steps was due a slight miscalculation)
Adding epsilon would re-introduce an exponential component to the search. In fact, epsilon = 3/4 gives you total power. But this is only relevant if the reduction (https://cstheory.stackexchange.com/a/4785) can be made precise enough to bound L, U to within a fixed small epsilon. It could even be the case that you can bound to an arbitrarily small epsilon, but only at the expense of exploding other parameters. (B, T, k).