Miller, Ramachandran and Kaltofen showed that any straight line program can be executed in parallel time O(log n) using M(n) processors where M(n) is the number of processors for multiplying nxn matrices in O(log n) time.

My question is this: suppose that the number of processors is constrained to be at most polylogarithmic. What is the best lower bound known for parallel complexity of straight-line code evaluation?


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.