When I am reading a paper I found a notation $\operatorname{poly}( |F|,n,$$\frac{1}{\epsilon}) $. Its not clear to me that what this notation represents. Can you please help me out?
Tell me more
×
Computer Science Stack Exchange is a question and answer site for
students, researchers and practitioners of computer science. It's 100% free, no registration required.
|
|
|||||
|
|
$F=\mathrm{poly}(n)$ means that $F$ is polynomial in $n$, i.e., that there exists a constants $c$ such that $F=\Theta(n^c)$. (sometimes it might mean upper-bounded by polynomial, that is $F=O(n^c)$) For multiple variable, the same applies, $\mathrm{poly}(n,m)$ means polynomial both in $n$ and $m$, that is, there are constants $c_1,c_2$ and the quantity is $\Theta(n^{c_1}m^{c_2})$. (again, the more common use is for $O(n^{c_1}m^{c_2})$) |
||||
|
|
$\mathrm{poly}(\cdot)$ is simply notation for a function that is polynomial with respect to its parameters. In your case it would be polynomial in terms of $|F|$, $n$, and $\frac{1}{\epsilon}$. |
|||
|
|
