1
$\begingroup$

I would like to know what $O(v(n))$ really means in detailed and simple words please. I found it everywhere in the literature I am reviewing but I cannot find what the intuition of it (especially if it means the Big O Notation, then what it has to do with the Probability here; also what is $v$, it is never defined except in another paper as a constant -but maybe not related directly to v in this formula-).

enter image description here

Many Thanks.

References 1 , 2

Improve this question
$\endgroup$
  • 2
    $\begingroup$ can you give a reference to where you got the quote from and what [1] is? after all, others may be better than you in tracing references. took a quick look at two references, I did not see any $\nu(n)$. $\endgroup$ – kodlu Aug 31 '20 at 22:24
  • $\begingroup$ @kodlu Just added the references. This (1) is the equation number whereas $s{_1}^{i-1}$ means the subsequence starting at the first bit and ends at $i-1$. $\endgroup$ – Mike Aug 31 '20 at 22:43
4
$\begingroup$

But this notation is defined (informally) in the first paper.

The notation $O(\nu(n))$ is used for any function, $f(n)$, that vanishes faster than the inverse of any polynomial, that is for every polynomial, $\mathrm{poly} (n)$, and $n$ large enough, $f(n) \leq 1/\mathrm{poly}(n)$

Therefore, what it means is no probabilistic polynomial time (PPT) algorithm $A$ can guess the next bit at inverse polynomially decreasing error rate.

Given any PPT algorithm $A$ this error probability decays super-polynomially, for example at a rate $\exp(-\log^2 n)$ which goes to zero faster than any polynomial.

Claim: $\exp(-\log^2 n)$ is less than $n^{-c}$ for any constant $c$ for $n$ large enough.

Proof: Look at the reciprocal. $$\exp(\log^2 n) > n^c$$ if and only if $$\log^2 n > c \log n$$ which will clearly happen as soon as $$\frac{\log^2 n}{\log n}>c$$ i.e., as soon as $\log n>c$.

Note that $\exp(\log^{1+\epsilon} n)$ is superpolynomial for all $\epsilon>0.$

Edit: The superpolynomial convergence is essentially what is referred to as negligibility.

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks and +1. So a successful predictor should predict with a probability greater than or equal $1-O(ν(n))$, How is the latter evaluated numerically. That's from where should I derive the $O(ν(n))$ numerically? A simple example of a simple algorithm will be very much appreciated. $\endgroup$ – Mike Sep 1 '20 at 9:57
  • $\begingroup$ Is O(v(n)) the error rate? And how is it derived? Practically from the experiment/simulation? Thanks. $\endgroup$ – Mike Sep 1 '20 at 10:38
  • 2
    $\begingroup$ It is implicitly negligibility. Adding this into answer will increase the awareness. $\endgroup$ – kelalaka Sep 1 '20 at 18:17
1
$\begingroup$

First, that's not the Next Bit Test, which is purely theoretical, but rather an attempt at a practical approximation of it.

From your first citation:

The notation $O(\nu(n))$ is used for any function, $f(n)$, that vanishes faster than the inverse of any polynomial, that is for every polynomial, $poly(n)$, and $n$ large enough, $f (n) < 1/poly (n)$.

So you can think of it as a function that asymptotically approaches 0, very, very quickly. Overall, this means that the probability in question must then be extremely small. Since that probability is |(the chance that an attacker guesses the next bit)-50%| it means the attacker has extremely small advantage.

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks for your answer. +1 for explaining the intuition of the notation. $\endgroup$ – Mike Sep 2 '20 at 9:17
  • $\begingroup$ Just to mention, the paper is a second attempt of the NBT, and based on improving a previous attempt and the Shamir's paper (which proves that the NBT proposed by Yao is not universal where Shamir provides a better version of the NBT) $\endgroup$ – Mike Sep 2 '20 at 10:05

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.