5
$\begingroup$

What does "hold uniformly" mean in the statement of Theorem 1.7 in A Faster Subquadratic Algorithm for Finding Outlier Correlations? Here's the theorem text ("hold uniformly" is in the last line):

enter image description here

$\endgroup$
  • 1
    $\begingroup$ I don't find it very clear in this context. Possibly what they mean is that the constants and log factors hidden in the $\tilde{O}$ do not change even if $n,\tau,\rho$ change. $\endgroup$ – usul Jul 19 '18 at 17:16
5
$\begingroup$

We say a bound on a family of objects holds uniformity if there is a single bound that applies to all objects in the family, as opposed to a bound that is dependent upon the parameter that determines which element of the family is under discussion.

For example, $f_n(x)= \sin(nx)$ is uniformly bounded by $1$, while $g_n(x)=n\cos(nx)$ is not. In fact, $g_n$ isn’t uniformly bounded by anything, as any bound on it needs to depend on $n$.

$\endgroup$
  • 2
    $\begingroup$ Not a typo, just subject-verb agreement. "The bounds hold" vs "the bound holds". (Hint: "running time" is a noun adjunct, not the subject.) $\endgroup$ – David Eppstein Jul 19 '18 at 6:08
  • $\begingroup$ Thanks, that's what I thought but I wanted to double check $\endgroup$ – Elliot Gorokhovsky Jul 19 '18 at 12:31
  • $\begingroup$ I don't think there's a typo. There are two bounds given, one in (2) and the other in the third line of text. So I think bounds plural is correct. $\endgroup$ – Elliot Gorokhovsky Jul 26 '18 at 18:01
  • 1
    $\begingroup$ @ElliotGorokhovsky Oh I see. You’re likely right. $\endgroup$ – Stella Biderman Jul 26 '18 at 18:02

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.