Home » Uncategorized » Learning a single-variable polynomial, or the power of adaptive queries

# Learning a single-variable polynomial, or the power of adaptive queries

Problem: Alice chooses a secret polynomial \$latex p(x)\$ with nonnegative integer coefficients. Bob wants to discover this polynomial by querying Alice for the value of \$latex p(x)\$ for some integer \$latex x\$ of Bob’s choice. What is the minimal number of queries Bob needs to determine \$latex p(x)\$ exactly?

Solution: Two queries. The first is \$latex p(1)\$, and if we call \$latex N = p(1) + 1\$, then the second query is \$latex p(N)\$.

To someone who is familiar with polynomials, this may seem shocking, and I’ll explain why it works in a second. After all, it’s very easy to prove that if Bob gives Alice all of his queries at the same time (if the queries are not adaptive), then it’s impossible to discover what \$latex p(x)\$ is using fewer than \$latex textup{deg}(p) + 1\$ queries. This is due to a fact called polynomial interpolation, which we’ve seen on this blog before…

View original post 351 more words