# How to find degree of polynomial represented as a circuit?

I know very little about arithmetic circuits, so maybe it is something well-known.

Given a small circuit consisted of $\{1,x,-,+,*\}$ defining one variable polynomial. Let be additionally known that degree of this polynomial does not exceed $d$ and all the coefficients are small. I wonder if exists a fast way to find actual degree of this polynomial? Using FFT and some small field, one can do it in $O(d)$ time (regardless $polylog$ factors), but this time is sufficiently to reconstruct the the entire polynomial, so I hope computing degree only can be done more efficient.

• does this involve polynomial identity testing and looking for the smallest degree polynomial that is equivalent?
– vzn
Aug 20, 2014 at 15:14
• I'm sorry, I don't get it. Aug 21, 2014 at 10:16
• afaik, iiuc, one can "multiply out" the entire DAG to get a polynomial. however, that may not be the minimal equivalent polynomial, hence PIT seems quite relevant...? not sure how that relates to your FFT algorithm. it would help if you cited the FFT algorithm you are referring to. are you familiar with O'Donnell analysis of boolean fns? odds are the answer is in there somewhere...
– vzn
Aug 21, 2014 at 15:05
• I've just started reading O'Donell, so I hope I'll find something useful there. By FFT algorithm I just mean, that you can compute polynomial in roots of unity of some small field (you can do it fast, as you a circuit is small) and than using inverse FFT extract all the coefficients of the polynomial. Of cause one can "multiply out" the entire DAG, but the question remind the same: how to extract degree from this expression? Aug 22, 2014 at 15:13

If the coefficients are small, then for large $x$ the polynomial is roughly equal to $Cx^d$. If you plug in both $x$ and, say, $2x$, then the ratio should be roughly $2^d$. Given bounds on the coefficients and the degree, this method can be made rigorous.

Another idea uses difference sequences. For a polynomial $P(x)$, the polynomial $P(x+1) - P(x)$ has degree smaller by one, the polynomial $P(x+2)-2P(x+1)+P(x)$ has degree smaller by two, and so on (in general, the coefficients are binomial coefficients with alternating signs). Using polynomial identity testing you can find the degree by binary search. This seems less efficient than your approach.

• Both methods look really nice, but if I'm right both require O(d) time: 1) you need to storage exponential in d numbers 2) you need to construct a new circuit of size O(d) and run polynomial identity testing. Do I understand correctly? Aug 21, 2014 at 6:15
• You're probably right, though it should be $O(d)$ evaluations of the circuit rather than $O(d)$ time. Aug 21, 2014 at 12:50
• You are right, I hide all the logarithmic factors including size of the circuit. Aug 21, 2014 at 13:24