I've come across this interesting inequalities problem recently, which seemed straight-forward at first glance but has proven interesting enough to ask about it here.

Suppose you are given the degree of an unknown polynomial, and are told that all the coefficients are integers and are all within $min \le a\_k \le max$. Also, you have access to an oracle who will evaluate p(q), the unknown polynomial, and compare it to your guess $g\_q$, where q is the number of previous guesses you have made, and determine if your guess was less, greater than, or exactly equal to the unknown polynomial.

What is the optimal method of choosing guesses, given previous results, in order to make a correct guess as soon as possible in the worst case?

If the degree is d and the coefficients are bounded by [min, max] then it would seem the best possible method would require slightly less than $ \frac {d \log (max - min + 1)}{\log 2}$ by binary search. Its slightly less because with an answer of > from the oracle, you exclude both the values less than and those equal to the guess, which could be more than 50% of possibilities.

If the median of the evaluated values at q of all of the remaining possible polynomials can be found, than guessing that value would be guaranteed to eliminate at least half of the possibilities. But is there any efficient way to find the median of a function of a set of polynomials that are only identified by inequalities?

For the first guess, q is zero and therefore all but the constant term of the polynomial are irrelevant. It makes sense then to make g(0) to be $\frac {min + max}{2}$. But after that, the best way of finding the median quickly seems elusive.

As an example, make min = -100, max = 100 and d = 1. $\frac {-100 + 100}{2}$ = 0, so g(0) should be 0. If the oracle returns > then we know $0 < a\_0 \le 100$ or $1 \le a\_0 \le 100$ since we are dealing with integer coefficients.

An ideal method would include an efficient way to find the median and characterize the set of possibilities given the previous answers from the oracle. But medians can be hard to calculate so an efficient method to calculate the mean of p(q) for the set of possibilities would be close enough if an efficient method doesn't exist for medians.

  • $\begingroup$ What are p and g? $\endgroup$ – Qiaochu Yuan Feb 1 '10 at 16:16
  • 1
    $\begingroup$ p is (obviously) the unknown polynomial. g is (as stated) your guess. $\endgroup$ – TonyK Feb 1 '10 at 17:10
  • $\begingroup$ I can replace the g(q) notation with $g\_q$ if that makes more sense to use subscript notation. I was just trying to describe the set of guesses made in a compact way. Each guess of course depends on the answer from the previous one, so I can see why describing at as a function is confusing. $\endgroup$ – Anthony Peterson Feb 1 '10 at 20:55
  • $\begingroup$ 1) The best method does not have to use medians because it is conceivable that what is lost at a given step is regained at the next step. 2) A sensible approach might be to try proving that using means is a good algorithm, but though looking simpler, even finding a mean is a hard computational problem since it amounts to integration of a polynomial on a polyhedron. This is a computationally hard problem: see for example math.ucdavis.edu/~deloera/RECENT_WORK/integrationsimplex.pdf $\endgroup$ – Boris Bukh Feb 1 '10 at 21:14

Just determine the coefficient at the highest power first by plugging in huge numbers and doing binary search (comparing to what you'd get for the half-integer coefficients). Once you know it, you can easily figure out the coefficient at the next power in the same way and so on.

Now, if you also have a bound on $q$ you can plug in, it becomes interesting.

Oops, sorry for misunderstanding.

OK, you can easily do $Cd^M\log N$ then. The trick is that no matter how you split the d-dimensional simplex of volume 1 by a hyperplane through its center and no matter which piece you'll take, you'll be able to find a simplex of volume $1-d^{-m}$ conatining this piece where $m$ is some fixed number, which I will need some time to compute precisely (my educated guess would be m=4). Now just use this fact to obtain a simplex of either volume less than $N^{-2d}$ or with one vertex outside the ball of radius $N^{3d}$ containing the set of remaining polynomials after just $O(d^M\log N)$ steps. In both cases, you'll be able to find a linear dependence between the coefficients that is precise up to $N^{-2}$, which means that you can eliminate one coefficient from the polynomial entirely (the $d$-th power of the variable is still well below $N$, so the precision is enough to distinguish the integer values and each exactly attained equality which will not allow you to tell for sure which half you are in gives you food for interpolation).

Sorry if it is too sketchy. I'll try to edit it into something more reasonable later unless somebody gives a better solution.

| cite | improve this answer | |
  • $\begingroup$ The question was that one can ask question about q(0), then about q(1), then about q(2), etc. One cannot ask question about arbitrary values in arbitrary order. $\endgroup$ – Boris Bukh Feb 1 '10 at 21:58
  • $\begingroup$ Yeah, if you can compare your guess to arbitrary k in p(k) then your technique works. You can go backwards, from the lowest power as well. But my curiosity was based on the idea that you can't pick what x is in p(x), you have to use all different values of x, and therefore its the inequalities or some other representation of them that has to be worked with. $\endgroup$ – Anthony Peterson Feb 2 '10 at 2:30

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.