I'm currently reading the paper (Leveled) fully homomorphic encryption without bootstrapping , and the following paragraph was near the start:

What is meant by the symbol used? Is it merely to represent polynomial time or something else entirely?

  • $\begingroup$ Thanks for the edit, will make sure I follow proper posting practices in the future. $\endgroup$
    – Masutatsu
    Jul 18 '13 at 10:30
  • $\begingroup$ I added a link to a page about this article, unfortunately it is only available for pay. $\endgroup$ Jul 20 '13 at 20:31
  • $\begingroup$ There is another version of the paper (by the same authors) which goes into the same info - Fully Homomorphic Encryption without Bootstrapping $\endgroup$
    – mikeazo
    Jul 20 '13 at 20:43

As you probably know $f(\lambda)=O(\lambda^4)$ means that $|f|$ asymptotically upper bounded by some constant times $\lambda^4$. The notation $f(\lambda)=\Omega(\lambda^4)$ corresponds to an asymptotic lower-bound.

Now, the $\tilde O$ and $\tilde \Omega$ are closely related notations, where we not only ignore constants but also values which are polynomial in the logarithm of the argument.

So in your quotation, $\tilde\Omega(\lambda^4)$ refers to a function $f(\lambda)$ which is asymptotically lower bounded by something of the form $K \log(\lambda)^c \lambda^4$, where $K$ and $c$ are some non-specified constants. [I am ignoring the absolute value of $f$ from the definition, since it clear in your context that $f$ takes positive values.]


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.