Skip to main content
Theoretical Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

8
  • $\begingroup$ Is the Euclidean algorithm optimal amongst its peers? jstor.org/stable/3185191 $\endgroup$ Commented Feb 10 at 17:40
  • $\begingroup$ @Siddharth Thank you. I have seen that paper. Seeing it again is interesting because the depth lower bound they show is $>\frac1{10}\log_2\log_2 N$ while the conjecture is it is i.o. $\Omega(\log_2N)$. Also note this is an algebraic circuit with if condition .. sort of $VNC^1$ with 'if'. So if all $GCD$ algorithms use recursively the rem function, we have a Boolean lower bound against $L$ (that is they would have shown $GCD\not\in L$). So we have not ruled out there could be a different Boolean algorithm for $GCD$ in $L$ and algebraically in $VNC^1$. $\endgroup$ Commented Feb 10 at 19:47
  • $\begingroup$ Note that it is known that the polynomial GCD can be computed in piecewise $\mathsf{AC}⁰$, cf Constant-Depth Arithmetic Circuits for Linear Algebra Problems. $\endgroup$ Commented Feb 11 at 8:31
  • $\begingroup$ @Bruno Even multiplication is not known to be in AC^0! What is piecewise $AC^0$? Does it contain $TC^0$? $\endgroup$ Commented Feb 11 at 21:13
  • 1
    $\begingroup$ @Turbo It is for polynomials over a field. If you are interested, the paper is really nice to read! Maybe my first comment was misleading: I am not saying that the problem you mention is solved, I am linking to a recent related result, that's it. $\endgroup$ Commented Feb 12 at 15:33