Say $F(X) \in \mathbb{Z}[X]$ is an even degree polynomial of degree $2n$. 


One needs to evaluate $F(X)$ at $O(n)$ points to interpolate and get all the coefficients of $F(X)$. 


However say I need **only the coefficient of $X^{n}$ or $X^{2n}$** (the mid coefficient or the largest), do I still have to evaluate at $O(n)$ points? 


Will having coefficient of $X^{t}$ same as coefficient of $X^{2n-t}$ help in reducing the number of points from $O(n)$ to detect $X^{n}$ coefficient (mid-coefficient in the symmetric case)? 


Is this a well studied problem that has some good references - that is interpolating for only one or few coefficients?


There is one way to do this - evaluating at one large prime and reduction via modulo operations. However, this gives way too much information(that is I can get all the coefficients) and when I evaluate at a large prime, the word size become the order of $O(n\log(nM))$ where M is the largest coefficient size. So in a way we are still using $O(n^{1+\epsilon})$ operations.


I am guessing there should be a way to get only information about the single coefficient I am interested in while getting the operations down to $O(n^{1-\epsilon})$ at the 'cost of not-getting' information about other coefficients.


Say you have a polynomial of odd degree (even coeffcients). Evaluating at $1$ and $-1$ and adding the results or subtracting the results, localizes the information into groups of two coefficients. My question could be can we localize further? Supposing in addition I have $F(x) = A(x)B(x)$ where I know $A(x)$ and $B(x)$, is it possible to represent $A(x)$ and $B(x)$ in a different way so that I can somehow target the mid coefficient of $F(x)$ without getting other coefficients?



Interpolating for particular coefficients
I’ll turn my comment above into an answer, maybe it will make things more clear for the OP.


**Theorem:** Let $1\le m\le n$, $m\le k\le2n$, $a\_1,\dots,a\_k\in\mathbb Q$. Then there exist polynomials $A,B,\tilde A\in\mathbb Z[x]$ of degree $n$ such that $AB$ and $\tilde AB$ have distinct $k$th coefficient, but $A(a\_i)B(a\_i)=\tilde A(a\_i)B(b\_i)$ for every $i=1,\dots,m$.


**Proof:** Put $A=0$, $A'=cx^r\prod\_{i=1}^m(x-a\_i)$, $B=x^s$, where $k=m+r+s$, $r+m,s\le n$, and $c$ is chosen so that $A'$ has integer coefficients (i.e., $c$ is a multiple of the product of the denominators of the $a\_i$s).


Thus, if you want to extract the $k$th coefficient by evaluation at rational points, you absolutely need at least $k+1$ points, and therefore time $\Omega(k)$.


In fact, *any* algorithm for extraction of the $k$th coefficient of $AB$ needs time $\Omega(k)$. The reason is that the coefficient equals $\sum\_{i\le k}A\_iB\_{k-i}$, and therefore it *depends* on $2k+2$ of the input numbers in the sense that changing any of them can change the result. In fact, it will *always* change the result unless the matching coefficient in the product is $0$, thus even in the best possible case, we need to read at least one of $A\_i$ or $B\_{k-i}$ for every $i$ to fix the result, i.e., we need to use at least $k+1$ of the input numbers, and therefore we need time at least $k+1$. There is no way around it.


In view of this fact, it’s probably best to stick to direct evaluation of the formula $\sum\_{i=0}^kA\_iB\_{k-i}$, which computes the result using $k+1$ multiplications and $k$ additions. Since you need at least $k$ or so operations using any other method, this is pretty much optimal, and as an additional bonus it is simple and easy to implement.


More sofisticated methods (like evaluation and interpolation) are only useful if you need to extract *many* coefficients of the polynomial, because they save some repeated computations. They are not going to help you if you need just one coefficient.


