Data structures for distributed counting

DOI10.1016/0022-0000(84)90067-9MaRDI QIDQ794431zbMATH OpenOpenAlexFDO

Authors Martin Fürer

Publication date 1984

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(84)90067-9

zbMATH Keywords

simulationsdata structureshierarchy for k-tape Turing machinesredundant representation of integers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• New time hierarchy results for deterministic TMS
• Integer representation and counting in the bit probe model
• Integer Representation and Counting in the Bit Probe Model
• An inherent bottleneck in distributed counting
• Integer representations towards efficient counting in the bit probe model

Cites work

• scientific article; zbMATH DE number 3594649 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• scientific article; zbMATH DE number 3407150 (Why is no real title available?)
• On Time Versus Space
• On the Computational Complexity of Algorithms
• On time hierarchies
• Space bounds for a game on graphs
• Two-Tape Simulation of Multitape Turing Machines

Cited in

(7)

• Uniform normal form for general time-bounded complexity classes
• New time hierarchy results for deterministic TMS
• An inherent bottleneck in distributed counting
• A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
• Almost-everywhere complexity hierarchies for nondeterministic time
• A time hierarchy theorem for the LOCAL model
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory

This page was built for publication: Data structures for distributed counting

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