A tight ω(loglog n)-bound on the time for parallel RAM's to compute nondegenerated boolean functions

DOI10.1016/S0019-9958(82)90477-6zbMath0539.68038OpenAlexW2076058038MaRDI QIDQ3326839

Hans Ulrich Simon

Publication date: 1982

Published in: Information and Control (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0019-9958(82)90477-6

zbMATH Keywords

lower boundBoolean functionPRAMparallel random access machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (8)

Exact lower time bounds for computing Boolean functions on CREW PRAMs ⋮ A note on the size of minimal covers ⋮ On separating the EREW and CREW PRAM models ⋮ Unnamed Item ⋮ Sensitivity vs. block sensitivity (an average-case study) ⋮ Time lower bounds do not exist for CRCW PRAMs ⋮ Tight bounds on sensitivity and block sensitivity of some classes of transitive functions ⋮ New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity

This page was built for publication: A tight ω(loglog n)-bound on the time for parallel RAM's to compute nondegenerated boolean functions