Inverse function without the original function

55 Views Asked by At

I am going through this paper, 'Certifiable Quantum Dice Or, True Random Number Generation Secure Against Quantum Adversaries' by Vazirani and Vidick. In 'Our results' section on the page 2, it says:

Let $n$ be an integer, and $ε > 0$ a parameter such that $ε$ is at least an inverse polynomial in $n$.

My question is how can I know the inverse polynomial if I don't know the original polynomial? Wouldn't it be simpler if they had just said $ε$ is a function of $n$?

Update: There is a relation between $ε$ and $n$ on page 3. It is $ε = n^{-\alpha}$ where $n$ is an integer and $\alpha > 0$.

1

There are 1 best solutions below

0
On

By $\varepsilon$ is at least an inverse polinomial in $n$ they mean that $1/\varepsilon$ is at most a polinomial function of $n$ i.e. for some $\alpha>0$ $$ \varepsilon(n) > \frac{1}{n^\alpha} $$