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

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

Math ∩ Programming

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: