Bit complexity of breaking and achieving symmetry in chains and rings
DOI10.1145/1326554.1326557zbMATH Open1326.68035OpenAlexW1977127383MaRDI QIDQ3546359FDOQ3546359
Authors: Shlomo Moran, Sergio Rajsbaum, Yefim Dinitz 
Publication date: 21 December 2008
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1326554.1326557
Recommendations
- Bit complexity of breaking and achieving symmetry in chains and rings (extended abstract)
- The complexity of symmetry-breaking formulas
- Circuit complexity of symmetric Boolean functions in antichain basis
- scientific article; zbMATH DE number 4035741
- scientific article; zbMATH DE number 4062892
- scientific article; zbMATH DE number 165425
- Symmetric groups and quotient complexity of Boolean operations
- Long symmetric chains in the Boolean lattice
- Parameterized complexity results in symmetry breaking
- Decompositions of the Boolean lattice into rank-symmetric chains.
distributed computinglower boundsconsensusleader electioncommunication complexitybit complexitytight boundmessage complexitycommunication costprocessor ringprocessor chainsymmetric synchronous execution
Cited In (17)
- An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
- A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots
- Bit complexity of breaking and achieving symmetry in chains and rings (extended abstract)
- Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds
- Two absolute bounds for distributed bit complexity
- Trading bit, message, and time complexity of distributed algorithms
- Structural Information and Communication Complexity
- On the time and the bit complexity of distributed randomised anonymous ring colouring
- Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings
- Fast protocols for leader election and spanning tree construction in a distributed network
- The topology of randomized symmetry-breaking distributed computing
- Distributed communication complexity of spanning tree construction
- An optimal bit complexity randomized distributed MIS algorithm
- About randomised distributed graph colouring and graph partition algorithms
- Generalized symmetry breaking tasks and nondeterminism in concurrent objects
- Communication Complexity of Wait-Free Computability in Dynamic Networks
- Exact communication costs for consensus and leader in a tree
This page was built for publication: Bit complexity of breaking and achieving symmetry in chains and rings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3546359)
