1
$\begingroup$

If you remove LLL part then is remaining part of

a. Lenstra algorithm

b. Barvinok algorithm

in $O(f(n)(\log(mL))^c)$ time on $O(g(n)(mL)^c)$ processors with fixed $c>0$ in fixed $n$ dimension, $m$ constraints and $L$ bit length input for some functions $f,g:\Bbb R\rightarrow\Bbb R$?

Note we know linear programming and convex programming are not in $NC$ in general dimension.

|cite|improve this question
$\endgroup$
  • $\begingroup$ I assume for your last comment you mean assuming $P \neq NC$? $\endgroup$ – Joshua Grochow Apr 1 '18 at 23:42
  • $\begingroup$ @JoshuaGrochow yes that is correct. $\endgroup$ – Turbo Apr 2 '18 at 1:31

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.