A linear PRAM model is a PRAM model without bit operations and at least one operand of the $\times$ instruction is a constant. If in addition we require that the running time does not depend on the bit length of the input then the resulting model is called the arithmetic linear PRAM model.

This 1999 paper (ps file) of Ketan Mulmuley says "we do not know a natural example that is in the linear PRAM model but not in the arithmetic linear PRAM model". I am wondering if such an example is found in the last decade. Are there any potential candidates ?


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.