Cover Image

On the Dynamics of Bounded-Degree Automata Networks

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Aracena, Julio, Bridoux, Florian, Gadouleau, Maximilien, Guillon, Pierre, Perrot, Kévin, Richard, Adrien, Theyssier, Guillaume
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Hardness of monadic second-order formulae over succinct graphs
by: Gamard, Guilhem, et al.
Published: (2023)

On the complexity of freezing automata networks of bounded pathwidth
by: Goles, Eric, et al.
Published: (2025)

Circuit metaconstruction in logspace for Rice-like complexity lower bounds in ANs and SGRs
by: Goubault-Larrecq, Aliénor, et al.
Published: (2025)

Complexity of Multiple-Hamiltonicity in Graphs of Bounded Degree
by: Liu, Brian, et al.
Published: (2024)

On Factorization of Sparse Polynomials of Bounded Individual Degree
by: Chuyoon, Aminadav, et al.
Published: (2026)

Complexity of Boolean automata networks under block-parallel update modes
by: Perrot, Kévin, et al.
Published: (2024)

Feedback Set Problems on Bounded-Degree (Planar) Graphs
by: Bai, Tian, et al.
Published: (2026)

Rice-like complexity lower bounds for Boolean and uniform automata networks
by: Goubault-Larrecq, Aliénor, et al.
Published: (2024)

Timed Prediction Problem for Sandpile Models
by: Concha-Vega, Pablo, et al.
Published: (2025)

Property Testing in Bounded Degree Hypergraphs
by: Aaronson, Hugo, et al.
Published: (2025)

Simulating Weighted Automata over Sequences and Trees with Transformers
by: Rizvi, Michael, et al.
Published: (2024)

Complexity of the Freezing Majority Rule with L-shaped Neighborhoods
by: Concha-Vega, Pablo, et al.
Published: (2025)

Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions
by: Geniet, Colin, et al.
Published: (2026)

Visibly Recursive Automata
by: Dubrulle, Kévin, et al.
Published: (2026)

Structural Parameterizations for Two Bounded Degree Problems Revisited
by: Lampis, Michael, et al.
Published: (2023)

Deterministic Weighted Automata under Partial Observability
by: Michaliszyn, Jakub, et al.
Published: (2024)

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs
by: Dikstein, Yotam, et al.
Published: (2024)

Bounded Dynamic Level Maintenance for Efficient Logic Optimization
by: Liu, Junfeng, et al.
Published: (2025)

Approximate Degree Composition for Recursive Functions
by: Chakraborty, Sourav, et al.
Published: (2024)

Low-Degree Testing Over Grids
by: Amireddy, Prashanth, et al.
Published: (2023)

Nondeterministic Auxiliary Depth-Bounded Storage Automata and Semi-Unbounded Fan-in Cascading Circuits
by: Yamakami, Tomoyuki
Published: (2024)

Quantum Property Testing for Bounded-Degree Directed Graphs
by: Peng, Pan, et al.
Published: (2026)

Hilbert Functions and Low-Degree Randomness Extractors
by: Golovnev, Alexander, et al.
Published: (2024)

Low Degree Local Correction Over the Boolean Cube
by: Amireddy, Prashanth, et al.
Published: (2024)

Derandomizing Multivariate Polynomial Factoring for Low Degree Factors
by: Dutta, Pranjal, et al.
Published: (2024)

Counting Triangulations of Fixed Cardinal Degrees
by: Chambers, Erin, et al.
Published: (2025)

Resolution of The Linear-Bounded Automata Question
by: Lin, Tianrong
Published: (2021)

Low-Degree Polynomials Are Good Extractors
by: Alrabiah, Omar, et al.
Published: (2024)

Rigorous Implications of the Low-Degree Heuristic
by: Hsieh, Jun-Ting, et al.
Published: (2026)

Complexity of Fungal Automaton Prediction
by: Formenti, Enrico, et al.
Published: (2026)

A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions
by: Yao, Penghui, et al.
Published: (2025)

Trapping and commutative Boolean networks
by: Gadouleau, Maximilien
Published: (2026)

Polynomial Identity Testing and Reconstruction for Depth-4 Powering Circuits of High Degree
by: Shpilka, Amir, et al.
Published: (2026)

Tightening I/O Lower Bounds through the Hourglass Dependency Pattern
by: Eyraud-Dubois, Lionel, et al.
Published: (2024)

Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
by: Kothari, Pravesh K., et al.
Published: (2024)

Constant Degree Direct Product Testers with Small Soundness
by: Bafna, Mitali, et al.
Published: (2024)

Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
by: Byramji, Farzan, et al.
Published: (2025)

Fast Simulation of Cellular Automata by Self-Composition
by: Natal, Joseph, et al.
Published: (2024)

Unambiguous and Co-Nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters
by: Yamakami, Tomoyuki
Published: (2024)

Bounded-Depth Frege Lower Bounds for Random 3-CNFs via Deterministic Restrictions
by: Gryaznov, Svyatoslav, et al.
Published: (2024)