4
$\begingroup$

Given a primitive polynomial (gcd of coefficients is $1$) in $\Bbb Z[x]$ we have a polynomial time factoring algorithm for this that runs in time polynomial in degree $d$ and number of bits in coefficients. This is the Lenstra-Lenstra-Lovasz algorithm.

$1$. Arrange members of $\Bbb Z[x]$ with some bound on coefficients in some order. If I ask if the $t$th factor has $j$th bit in $i$th coefficient a $1$ is this algorithm known to give an $ACC^0$ circuit?

$2$. What is the smallest complexity class for the same query as $1$ if I say I only need at least in a randomized sense and for an algorithm that factors only a constant fraction of primitive polynomials?

Link https://mathoverflow.net/questions/258467/existence-of-randomized-polynomial-time-algorithm-and-some-arithmetic-analog-of/258477?noredirect=1#comment637557_258477.

$3$. Consider the overall Hensel lifting step in Zassenhaus' algorithm. If I ask is the $i$th digit has $j$th bit $1$ when lifting to $p^t$ can we have an $ACC^0$ circuit? Hensel lifting is just reading $p$-adic digits and may be this step is in $ACC^0$? If so Zassenhaus' algorithm would give $ACC^0$ circuit for thus answering $2$. There is a linear system interpretation here in section 8.1.2 https://www.nada.kth.se/~johanh/algnotes.pdf which might put the decision version in here to be in $ACC^0$.

Refer algorithm 10 and theorem 2 here http://www.mmrc.iss.ac.cn/~lzhi/Course/mchapter15.ps.

Please also check corollary $1.79$ here http://compalg.inf.elte.hu/~tony/KedvencKonyvek/InfoKonyvtar/03-Algorithms%20of%20Informatics%201,%202,%203/AlgofInfVol1Oct24.pdf for a log depth implementation of Hensel Lifting. Can it be reduced to constant depth?

$\endgroup$
  • $\begingroup$ What do you mean by an "arithmetic analog of ACC^0"? What's supposed to be the arithmetic analogue of modular counting gates? $\endgroup$ – Emil Jeřábek supports Monica Jan 1 '17 at 13:37
  • $\begingroup$ @EmilJeřábek sorry this is what I mean. I just want $O(\log^i n)$ depth and polynomial size of circuit with ring operations as gates for the arithmetic analog of $ACC^i$. $\endgroup$ – T.... Jan 1 '17 at 13:45
  • $\begingroup$ So it's actually an analogue of AC^i, not ACC^i. $\endgroup$ – Emil Jeřábek supports Monica Jan 1 '17 at 14:03
  • 1
    $\begingroup$ What's with all the "is this algorithm in ACC0?" questions? Maybe it would help to give some sense about what you are getting at with all of them. $\endgroup$ – Sasho Nikolov Jan 1 '17 at 21:16
  • 1
    $\begingroup$ NB: For poly-size circuits consisting only of ring operations (more traditionally known as "arithmetic circuits" or "algebraic circuits"), they can always be reduced to $O(\log^2 n)$ depth while maintaining poly-size. Also, your new edits to the question conflict with your earlier comment to Emil, since your (updated) question really is asking about bit complexity, not algebraic complexity. $\endgroup$ – Joshua Grochow Jan 2 '17 at 7:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.