0
$\begingroup$

Black box of $f(x)$ means I can evaluate the polynomial $f(x)$ at any point.

  • Input: A black box of monic polynomial $f(x) \in\mathbb{S}[x]$ of degree $d$.

  • Question : $\mathbb{S} \subseteq \mathbb{Z}$, unbounded from both sides

Here $\mathbb{S} \subseteq \mathbb{Z} $ is an interval unbounded from both sides. For example interval $(-b,\infty]$, where $b$ is any fixed value and this interval is bounded from left side. I am allowed to make only constant many queries to oracle. I want to find such an subset $\mathbb{S}$.

Unbounded interval: An interval is said to be left-bounded or right-bounded if there is some real number that is, respectively, smaller than or larger than all its elements. An interval is said to be bounded if it is both left- and right-bounded; and is said to be unbounded otherwise

Please give a reference to material also if possible. If anything is not clear please ask in the comments I will try clear it.

Motivation : Find a polynomial in two or three queries

$\endgroup$
  • 1
    $\begingroup$ Your title is not consistent with your question. Within constant number of queries, do you want to find the $d+1$ coefficients, or you want to find a interval $S$ as small as possible including all the coefficients? $\endgroup$ – Willard Zhan Oct 26 '17 at 19:13
  • 1
    $\begingroup$ 1. What is your question? Are you asking whether any algorithm at all exists? Are you asking for an efficient algorithm? Why isn't this answered by the answer to that other question? 2. What is an "interval unbounded from both sides"? The only such interval I know is $[-\infty,\infty]$, i.e., all of $\mathbb{Z}$. Do you perhaps mean that the interval is bounded on both sides (not unbounded)? $\endgroup$ – D.W. Oct 27 '17 at 4:21
  • $\begingroup$ @ Willard Zhan constant means not depends on input size (i.e. also not depends on $d$).$d+1$ queries are not constant queries. $\endgroup$ – Complexity Oct 27 '17 at 4:25
4
+50
$\begingroup$

If you don't know any bounds on the coefficients beforehand, then you cannot give them any bound without $d$ queries. Suppose you have made queries of $f(x)$ on $x=x_1,\ldots,x_{d-1}$, and claim that the coefficients of $f(x)$ are all at least $-b$. However, a different monic polynomial $f(x)-N(x-x_1)\cdots(x-x_{d-1})$ has the same evaluation on all the $d-1$ queries, and when $N$ is large enough the coefficient of $x^{d-1}$ in this polynomial must be smaller than $-b$, leading to a contradiction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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