2017 · 33 citations · 33 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationAlgorithmic ComplexityCombinatorial OptimizationComplexity TheoryComputational ComplexityTime ComplexityComplexity ClassesComplexity-theoretic HardnessComputational Complexity Of Graph AlgorithmsParameterized Complexity Classes
LCLs or locally checkable labelling problems (e.g. maximal independent set, maximal matching, and vertex colouring) in the LOCAL model of computation are very well-understood in cycles (toroidal 1-dimensional grids): every problem has a complexity of O(1), Θ(log* n), or Θ(n), and the design of optimal algorithms can be fully automated. This work develops the complexity theory of LCL problems for toroidal 2-dimensional grids. The complexity classes are the same as in the 1-dimensional case: O(1), Θ(log* n), and Θ(n). However, given an LCL problem it is undecidable whether its complexity is Θ(log* n) or Θ(n) in 2-dimensional grids.
33
Theory of Self-Reproducing Automata
Jacob T. Schwartz, John von Neumann, Arthur W. Burks · Mathematics of Computation · 1967 · 5.5K citations
Martin Gardner · Scientific American · 1970 · 1.6K citations
Solomon W. Golomb, Branko Grünbaum, G. C. Shephard · American Mathematical Monthly · 1988 · 1.4K citations
Locality in Distributed Graph Algorithms
Nathan Linial · SIAM Journal on Computing · 1992 · 885 citations
Proving Theorems by Pattern Recognition - II
Hao Wang · Bell System Technical Journal · 1961 · 871 citations