3 papers
cs.CC2020
Lower Bounds and Hardness Magnification for Sublinear-Time Shrinking Cellular Automata
Augusto Modanese
The minimum circuit size problem (MCSP) is a string compression problem with a parameter in which, given the truth table of a Boolean function over inputs of length , one mu…
cs.CC2019
Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata
Augusto Modanese
After an apparent hiatus of roughly 30 years, we revisit a seemingly neglected subject in the theory of (one-dimensional) cellular automata: sublinear-time computation. The model c…
cs.CC2019
Complexity-Theoretic Aspects of Expanding Cellular Automata
Augusto Modanese
The expanding cellular automata (XCA) variant of cellular automata is investigated and characterized from a complexity-theoretical standpoint. An XCA is a one-dimensional cellular…