Positive integers $d$, $H$ are given. It's known that $r\in(0,1)$ is such that $p(r)=0$ for some nonzero $p\in\mathbb Z[x]$ with $\deg p\leq d$ and coefficients $c_i$, such that $|c_i|\le H$, $i=0,\ldots,d$ (i.e. $H$ is a height of $p$). Since the set of such polynomials is finite, it's possible to guess $r$ by finite set of its binary digits.
What are the best known bounds on $n=n(d,H)$, such that there is $\{s_1,\ldots,s_n\}\subset\mathbb Z$ for which there is a unique $r$ with given binary digits $(r_{s_1},\ldots,r_{s_n})\in\{0,1\}^n$? (Here, $r_k=([2^kr]\;(\mathrm{mod}\;2)$ is the $k$-th binary digit of $r$). What if one assume $s_i=i$?
There is an obvious bound $n(1,H)=O(\max_{2\nmid k\le H}\{\mathrm{ord}_k(2)\})\le O(\log H)$, $H\to\infty$. Also the bound $n(d,H)=O(d^2+d\log H)$ is given in this paper by R. Kannan, A. K. Lenstra and L. Lovász. Is it the best known bound? Are there any lower bounds for $n(d,H)$?