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 that you have read and understand our privacy policy and code of conduct.