What is meant by $\operatorname{poly}(|F|, n, e)$?

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?

• What was the context?
– Raphael
Jan 30 '13 at 13:16

$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})$)
• Maybe it would be helpful to add that by $\mathrm{poly}(|F|)$ we mean polynomial in the input size of $F$, i.e., the size of the encoding of $F$ as given to the algorithm. Furthermore, another common (ab)use of notation for $O(n^c)$ is $n^{O(1)}$. Jan 30 '13 at 15:52
$\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}$.