Lower bounds and hardness magnification for sublinear-time shrinking cellular automata
From MaRDI portal
Publication:2117099
DOI10.1007/978-3-030-79416-3_18OpenAlexW3175558710MaRDI QIDQ2117099
Publication date: 21 March 2022
Full work available at URL: https://arxiv.org/abs/2007.12048
cellular automatastreaming algorithmsminimum circuit size problemhardness magnificationsublinear-time computation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fast language acceptance by shrinking cellular automata
- Fast parallel language recognition by cellular automata
- On the structure of one-tape nondeterministic Turing machine time hierarchy
- Parallel language recognition in constant time by cellular automata
- Cellular automata and communication complexity
- Complexity-theoretic aspects of expanding cellular automata
- Shrinking and Expanding Cellular Automata
- Circuit minimization problem
- A Padding Technique on Cellular Automata to Transfer Inclusions of Complexity Classes
- Amplifying lower bounds by means of self-reducibility
- A model of computation for VLSI with related complexity results
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Leader election in d-dimensional CA in time diam log(diam)
- Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata
- Hardness magnification near state-of-the-art lower bounds
- Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
- Computational Complexity
- Shrinking One-Way Cellular Automata
- Complexity of One-Way Cellular Automata
- Computational Complexity
This page was built for publication: Lower bounds and hardness magnification for sublinear-time shrinking cellular automata
