Lower bounds and hardness magnification for sublinear-time shrinking cellular automata
From MaRDI portal
Publication:2117099
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
Cites work
- scientific article; zbMATH DE number 3610741 (Why is no real title available?)
- scientific article; zbMATH DE number 1555206 (Why is no real title available?)
- scientific article; zbMATH DE number 7561750 (Why is no real title available?)
- scientific article; zbMATH DE number 7650418 (Why is no real title available?)
- A Padding Technique on Cellular Automata to Transfer Inclusions of Complexity Classes
- A model of computation for VLSI with related complexity results
- Amplifying lower bounds by means of self-reducibility
- Cellular automata and communication complexity
- Circuit minimization problem
- Complexity of one-way cellular automata
- Complexity-theoretic aspects of expanding cellular automata
- Computational Complexity
- Computational Complexity
- Fast language acceptance by shrinking cellular automata
- Fast parallel language recognition by cellular automata
- Hardness magnification near state-of-the-art lower bounds
- Leader election in d-dimensional CA in time diam log(diam)
- On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity
- On the structure of one-tape nondeterministic Turing machine time hierarchy
- Parallel language recognition in constant time by cellular automata
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Shrinking One-Way Cellular Automata
- Shrinking and expanding cellular automata
- Sublinear-time language recognition and decision by one-dimensional cellular automata
- Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
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)
