I had a brief look at "On Defining Proofs of Knowledge" by Bellare and Goldreich and I am a little confused by their definitions.

I was under the impression a negligible function $f$ was defined as something like $$\forall\ polynomials\ p\ \exists k\ s.t.\ \forall x > k: f(x) < \frac{1}{p(x)}$$

And that non-negligible meant simply that it was not negligible. The paper however states: "Put in other words negligible is not the negation of non-negligible!" (p. 5) And this seems to be based on the definition "a non-negligible function in $n$ is a function which is asymptotically bounded from below by a function of the form $n^{-c}$ for some constant $c$" (p. 4) which I am losely translating as $$\exists\ polynomial\ p\ and\ k\ s.t.\ \forall x > k: f(x) > \frac{1}{p(x)}$$ With the difference being functions which are somehow alternating.

This is a bit of a weird question because the mathematics seem to be clear but I am confused by what the common usage is. And is this something that is generally important? I've never seen it discussed elsewhere.

  • 2
    $\begingroup$ What they seem to be calling "non-negligible" (I can't check the ps file on mobile) is usually called "noticable" and the standard caution is that "non-negligible" (in the sense you used it) is not equivalent to "noticable". $\endgroup$
    – Maeher
    May 17 at 13:14
  • 2
    $\begingroup$ See e.g. these lecture notes $\endgroup$
    – Maeher
    May 17 at 13:24
  • $\begingroup$ Or page 9 of these $\endgroup$
    – Maeher
    May 17 at 13:30
  • $\begingroup$ Yes, that is the problem with the negation of complex sentences. $\endgroup$
    – kelalaka
    May 17 at 14:29

1 Answer 1

  • Negligible Function: A function $\mu$ is negligible iff $\forall c \in N \;\; \exists n_0 \in N$ such that $\forall n \geq n_0, \mu(n) < n^{−c}.$

    As we generally now, a negligible function is smaller than any polynomial. We have also an equivalent limit definition;

    $f(n)$ is negligible than for every polynomial $q(n)$ we have;

    $$\lim_{n \rightarrow \infty} q(n) f(n) =0$$

    The easy examples are the $2^{-n},2^{-\sqrt{n}}, \text{ and } n^{- \log n}$.

  • Non-Negligible Function:* a function $\mu(n)$ is non-negligible iff $\exists c \in N$ such that $\forall n_0 \in N, \exists n \geq n_0$ such that $\mu(n) \geq n^{-c}.$

    To be non-negligible, only one candidate is enough to show that $n \geq n_0$ for which $\mu(n) \geq n^{-c}$.

  • Noticeable Function: A function $\mu$ is noticeable iff $\exists c \in N, n_0 \in N$ such that $\forall n \geq n_0, \mu(n) \geq n^{-c}.$

    As we can see, the difference from non-negligibility is; for all $n \geq n_0$

    An example is $n^{-3}$ which is only polynomially slow ( like any polynomial)

    Weak One-Way Functions are defined on noticeable functions.

Interleaving is the key to generating distinguishing examples. Take any noticeable and negligible function and interleave them;

$$\mu(n) = \cases{ 2^{-n} & : $x$ is even \\ n^{-3} & : $x$ is odd}$$

$\mu$ is a non-negligible and non-noticeable function!.

*Quantifiers negation: In the negation $\neg\forall = \exists$ and $\neg \exists = \forall$

  • $\begingroup$ Based on the comments, I've given a shot that our site has this written around... $\endgroup$
    – kelalaka
    May 17 at 19:31
  • $\begingroup$ This answer does not address the fact that the cited paper defines non-negligible differently. $\endgroup$
    – Maeher
    May 17 at 19:53
  • $\begingroup$ @Maeher I'm aware of this. These definitions are the same as in Oded Goldreich's Foundations of Cryptography Volume I. So, I can say this is common usage as OP asked. If we consider the date of the article as '92 and the book as '01-03 we can say that this is common then ( Oded co-auther of the article and the sole author of the book) $\endgroup$
    – kelalaka
    May 17 at 20:03

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.