Computing OR on a randomized fixed adversary CRCW PRAM

DOI10.1016/S0020-0190(97)00102-6MaRDI QIDQ287164zbMATH OpenOpenAlexFDO

Authors Luděk Kučera

Publication date 26 May 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(97)00102-6

zbMATH Keywords

analysis of algorithmsparallel algorithmsconcurrent write PRAM

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Parallel algorithms in computer science (68W10)

Recommendations

• \(O (\log^* n)\) algorithms on a Sum-CRCW PRAM
• Time lower bounds do not exist for CRCW PRAMs
• scientific article; zbMATH DE number 1308942
• scientific article; zbMATH DE number 2081080
• Practical construction and analysis of pseudo-randomness primitives
• On the bit security of cryptographic primitives
• Randomness complexity of private circuits for multiplication
• Computationally Sound Formalization of Rerandomizable RCCA Secure Encryption
• A fast and simple partially oblivious PRF, with applications

Cites work

• scientific article; zbMATH DE number 512845 (Why is no real title available?)
• Parallel computation and conflicts in memory access

Cited in

(5)

• Achieving optimal CRCW PRAM fault-tolerance
• \(O (\log^* n)\) algorithms on a Sum-CRCW PRAM
• scientific article; zbMATH DE number 7650434 (Why is no real title available?)
• Doubly half-injective PRGs for incompressible white-box cryptography
• Time lower bounds do not exist for CRCW PRAMs

This page was built for publication: Computing OR on a randomized fixed adversary CRCW PRAM

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q287164)