Data structures for distributed counting

DOI10.1016/0022-0000(84)90067-9zbMATH Open0541.68025OpenAlexW2062246109MaRDI QIDQ794431FDOQ794431

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

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

zbMATH Keywords

simulationsdata structureshierarchy for k-tape Turing machinesredundant representation of integers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• On the Computational Complexity of Algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Time Versus Space
• Two-Tape Simulation of Multitape Turing Machines
• Space bounds for a game on graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On time hierarchies

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)