Sublinear-Time Probabilistic Cellular Automata

Augusto Modanese*

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu

15 Lataukset (Pure)

Abstrakti

We propose and investigate a probabilistic model of sublinear-time one-dimensional cellular automata. In particular, we modify the model of ACA (which are cellular automata that accept if and only if all cells simultaneously accept) so that every cell changes its state not only dependent on the states it sees in its neighborhood but also on an unbiased coin toss of its own. The resulting model is dubbed probabilistic ACA (PACA). We consider one- and two-sided error versions of the model (in the same spirit as the classes RP and BPP) and establish a separation between the classes of languages they can recognize all the way up to o(√n) time. As a consequence, we have a Ω(√n) lower bound for derandomizing constant-time one-sided error PACAs (using deterministic ACAs). We also prove that derandomization of T(n)-time PACAs (to polynomial-time deterministic cellular automata) for various regimes of T(n) = ω(log n) implies non-trivial derandomization results for the class RP (e.g., P = RP). The main contribution is an almost full characterization of the constant-time PACA classes: For one-sided error, the class equals that of the deterministic model; that is, constant-time one-sided error PACAs can be fully derandomized with only a constant multiplicative overhead in time complexity. As for two-sided error, we identify a natural class we call the linearly testable languages (LLT) and prove that the languages decidable by constant-time two-sided error PACAs are “sandwiched” in-between the closure of LLT under union and intersection and the class of locally threshold testable languages (LTT).

AlkuperäiskieliEnglanti
Otsikko40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023
ToimittajatPetra Berenbrink, Patricia Bouyer, Anuj Dawar, Mamadou Moustapha Kante
KustantajaSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (elektroninen)978-3-95977-266-2
DOI - pysyväislinkit
TilaJulkaistu - 1 maalisk. 2023
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaSymposium on Theoretical Aspects of Computer Science - Hamburg, Saksa
Kesto: 7 maalisk. 20239 maalisk. 2023
Konferenssinumero: 40

Julkaisusarja

NimiLeibniz International Proceedings in Informatics, LIPIcs
Vuosikerta254
ISSN (painettu)1868-8969

Conference

ConferenceSymposium on Theoretical Aspects of Computer Science
LyhennettäSTACS
Maa/AlueSaksa
KaupunkiHamburg
Ajanjakso07/03/202309/03/2023

Sormenjälki

Sukella tutkimusaiheisiin 'Sublinear-Time Probabilistic Cellular Automata'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä