4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ does this involve polynomial identity testing and looking for the smallest degree polynomial that is equivalent? $\endgroup$ – vzn Aug 20 '14 at 15:14
  • $\begingroup$ I'm sorry, I don't get it. $\endgroup$ – ivmihajlin Aug 21 '14 at 10:16
  • $\begingroup$ 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... $\endgroup$ – vzn Aug 21 '14 at 15:05
  • $\begingroup$ 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? $\endgroup$ – ivmihajlin Aug 22 '14 at 15:13
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – ivmihajlin Aug 21 '14 at 6:15
  • $\begingroup$ You're probably right, though it should be $O(d) $ evaluations of the circuit rather than $O(d) $ time. $\endgroup$ – Yuval Filmus Aug 21 '14 at 12:50
  • $\begingroup$ You are right, I hide all the logarithmic factors including size of the circuit. $\endgroup$ – ivmihajlin Aug 21 '14 at 13:24

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.