Given a set of $n$ linear inequalities in $d$ variables where the coefficients are integers of size bounded by $O(\log{n})$ is there a known deterministic parallel algorithm that runs in time $(d\log{n})^{O(1)}$ time using $2^{O(d)}n^{O(1)}$ or even $2^{d^{O(1)}}n^{O(1)}$ number of processors?

Notice, that I am not interested in the sequential complexity of this problem which is well studied with polynomial in $n$ (and exponential in $d$) algorithms known.

Also, Lin-Kriz and Pan prove that the problem is $\mathsf{NC}$ equivalent to Euclidean GCD (and therefore not known or expected to be in $\mathsf{NC}$) but I think their reduction from EGCD to this problem uses large numbers while I stipulate that the coefficients are small integers.



Your Answer

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