3
$\begingroup$

Given a polynomial $p(x_1,\ldots, x_k)$ in $k$ variables with maximum degree $n$, and $x_1,\ldots, x_k \in [0,1]$. Suppose $\max_{x \in [0,1]^k} p(x) = 1$, can we get an upper bound on the probability $\mathbb{P}(|p(x)| < \epsilon)$ where we treat the product space $[0,1]^k$ as a natural probability space? Using techniques from this paper: one can show that the above probability is small provided $\epsilon$ is of tower exponential order $e^{-e^n}$. But I need $\epsilon$ to be of poly-exponential order, i.e., $e^{-(nk)^c}$. Looking at the polynomial $x_1^n x_2^n \ldots x_k^n$, one deduce by central limit theorem that $\mathbb{P}(|p(x)| < \epsilon)$ is small provided $\epsilon = \mathcal{O}(e^{-kn})$. But I can't prove that this polynomial has the the highest probability of staying near zero.

If needed, one can also bound $\epsilon$ in terms of the total degree, i.e., the sum of degrees of all the monomial terms in $p$.

$\endgroup$

1 Answer 1

2
$\begingroup$

I believe that the result you want follows from the results in this very cool paper. (see, in particular page 9). There are probably improvements since then...

$\endgroup$
1
  • $\begingroup$ That's exactly the literature I am looking for. Thank you so much! $\endgroup$
    – John Jiang
    Dec 28, 2011 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.