3
$\begingroup$

I searched a lot but couldn't find a good resource that addresses this question. Given a boolean polynomial with $n$ boolean variables as a black box, what is the most efficient way to compute its degree? I am allowing randomized algorithms here.

Can you please provide references for both classical and quantum algorithms? What happens if we can compute polynomial in any $\mathbb{Z}_p$ through the black box.

Improve this question
$\endgroup$
3
  • $\begingroup$ Doesn't a classical algorithm per force have to look at all the points of the domain, since every boolean function on $n$ variables is representable as a degree-$n$ polynomial? That means that you can't beat $2^n$ queries and I suspect that the time to determine degree from that set is at worst polynomially bounded in the number of points, so you're looking at 'just' exponentially many operations to go with your exponentially many queries. $\endgroup$
    – Steven Stadnicki
    May 30, 2022 at 19:33
  • $\begingroup$ @StevenStadnicki I also think the classical version should be exponential. But I found this math.stackexchange.com/questions/1911026/… $\endgroup$
    – Math-fort
    May 30, 2022 at 21:09
  • $\begingroup$ please fully specify your conditions, why wasn't the link given in the question itself? $\endgroup$
    – kodlu
    May 31, 2022 at 11:43

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.