Lower bounds and hardness magnification for sublinear-time shrinking cellular automata
From MaRDI portal
Publication:2117099
DOI10.1007/978-3-030-79416-3_18OpenAlexW3175558710MaRDI QIDQ2117099FDOQ2117099
Authors: Augusto Modanese 
Publication date: 21 March 2022
Full work available at URL: https://arxiv.org/abs/2007.12048
Recommendations
- On the reduction of computational complexity of cellular automata
- A note on minimal Boolean formula size of one-dimensional cellular automata
- On the computational complexity of finite cellular automata
- A Nontrivial Lower Bound for an NP Problem on Automata
- scientific article; zbMATH DE number 1738667
- Lower bounds for the size of nondeterministic circuits
- Automata, Languages and Programming
- Subexponential Time and Fixed-parameter Tractability: Exploiting the Miniaturization Mapping
- Subexponential Time and Fixed-Parameter Tractability: Exploiting the Miniaturization Mapping
- Sub-Turing reducibilities of restricted complexity
cellular automatastreaming algorithmsminimum circuit size problemhardness magnificationsublinear-time computation
Cites Work
- Computational Complexity
- Computational Complexity
- Parallel language recognition in constant time by cellular automata
- Fast parallel language recognition by cellular automata
- Amplifying lower bounds by means of self-reducibility
- Circuit minimization problem
- On the structure of one-tape nondeterministic Turing machine time hierarchy
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Cellular automata and communication complexity
- Leader election in d-dimensional CA in time diam log(diam)
- Title not available (Why is that?)
- A model of computation for VLSI with related complexity results
- Fast language acceptance by shrinking cellular automata
- On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity
- Complexity-theoretic aspects of expanding cellular automata
- Complexity of one-way cellular automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- Hardness magnification near state-of-the-art lower bounds
- Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
- Shrinking and expanding cellular automata
- A Padding Technique on Cellular Automata to Transfer Inclusions of Complexity Classes
- Sublinear-time language recognition and decision by one-dimensional cellular automata
- Title not available (Why is that?)
- Shrinking One-Way Cellular Automata
This page was built for publication: Lower bounds and hardness magnification for sublinear-time shrinking cellular automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117099)
