What does it mean when saying "we want $\Lambda$ to be $\tilde{O}(1)$ as a function of $M$"? (it appears on the top of page 12 of this paper)

  • $\begingroup$ O-tilde omits log-bounded terms. $\endgroup$ – Juho Apr 27 '19 at 22:40

The notation $\tilde{O}(f(n))$ is not completely standard and is usually defined as $\tilde{O}(f(n)) = O( f(n) \cdot \text{poly} \log f(n))$. The intuition is that it drops factors that are asymptotically not larger than a polylogarithm of the argument. For example, you can write $\tilde{O}(n^2)$ in place of $O(n^2 \frac{\log^3 n}{\log \log n})$.

That said, in your paper $\tilde{O}(f(n))$ seems to be used as a shorthand for $O( f(n) \cdot \text{poly} \log n)$, although I was not able to find a definition within the paper by quickly skimming it. This only differs from the previous definition when $f(n)$ is smaller than or larger than any polynomial.

In the specific sentence you are quoting, the authors want $\Lambda$ to be in $O(\text{poly} \log M)$.


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.