Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
Thanks for the edit, will make sure I follow proper posting practices in the future. –  user7378 Jul 18 '13 at 10:30
    
I added a link to a page about this article, unfortunately it is only available for pay. –  Paŭlo Ebermann Jul 20 '13 at 20:31
    
There is another version of the paper (by the same authors) which goes into the same info - Fully Homomorphic Encryption without Bootstrapping –  mikeazo Jul 20 '13 at 20:43
add comment

1 Answer 1

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.]

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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