<blockquote>
<p>If you remove LLL part then is remaining part of</p>
<p>a. Lenstra algorithm</p>
<p>b. Barvinok algorithm</p>
<p>in <span class="math-container">$O(f(n)(\log(mL))^c)$</span> time on <span class="math-container">$O(g(n)(mL)^c)$</span> processors with fixed <span class="math-container">$c&gt;0$</span> in fixed <span class="math-container">$n$</span> dimension, <span class="math-container">$m$</span> constraints and <span class="math-container">$L$</span> bit length input for some functions <span class="math-container">$f,g:\Bbb R\rightarrow\Bbb R$</span>?</p>
</blockquote>
<p>Note we know linear programming and convex programming are not in <span class="math-container">$NC$</span> in general dimension.</p>
<p>In fact if we remove <span class="math-container">$LLL$</span> are these in <span class="math-container">$Logspace$</span>?</p>

CC BY-SA 3.0
2018-04-01T23:42:06.333Z
I assume for your last comment you mean assuming $P \neq NC$?
Joshua Grochow
CC BY-SA 3.0
2018-04-02T01:31:07.890Z
@JoshuaGrochow yes that is correct.
Turbo
<cc.complexity-theory><dc.parallel-comp><integer-programming><fixed-parameter-tractable><comp-number-theory>
Fixed dimension Integer programming minus LLL in fixed parameter $NC$?
Turbo
# Fixed dimension Integer programming minus LLL in fixed parameter $NC$?

(Asked by: username_0 on 2018-04-01)

> 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.

In fact if we remove $LLL$ are these in $Logspace$?

**Tags:** cc.complexity-theory, dc.parallel-comp, integer-programming, fixed-parameter-tractable, comp-number-theory
> **Comments:**
> **username_1**: I assume for your last comment you mean assuming $P \neq NC$?  
> **username_0**: @JoshuaGrochow yes that is correct.  

---

## 0 answers

