Zobrazeno 1 - 10
of 29
pro vyhledávání: '"Modanese, Augusto"'
Autor:
Dhar, Anubhav, Kujawa, Eli, Lievonen, Henrik, Modanese, Augusto, Muftuoglu, Mikail, Studený, Jan, Suomela, Jukka
The randomized online-LOCAL model captures a number of models of computing; it is at least as strong as all of these models: - the classical LOCAL model of distributed graph algorithms, - the quantum version of the LOCAL model, - finitely dependent d
Externí odkaz:
http://arxiv.org/abs/2409.13795
Autor:
Balliu, Alkida, Ghaffari, Mohsen, Kuhn, Fabian, Modanese, Augusto, Olivetti, Dennis, Rabie, Mikaël, Suomela, Jukka, Uitto, Jara
By prior work, we have many results related to distributed graph algorithms for problems that can be defined with local constraints; the formal framework used in prior work is locally checkable labeling problems (LCLs), introduced by Naor and Stockme
Externí odkaz:
http://arxiv.org/abs/2407.05445
Autor:
Akbari, Amirreza, Coiteux-Roy, Xavier, d'Amore, Francesco, Gall, François Le, Lievonen, Henrik, Melnyk, Darya, Modanese, Augusto, Pai, Shreyas, Renou, Marc-Olivier, Rozhoň, Václav, Suomela, Jukka
We extend the theory of locally checkable labeling problems (LCLs) from the classical LOCAL model to a number of other models that have been studied recently, including the quantum-LOCAL model, finitely-dependent processes, non-signaling model, dynam
Externí odkaz:
http://arxiv.org/abs/2403.01903
Autor:
Modanese, Augusto, Yoshida, Yuichi
Inspired by the works of Goldreich and Ron (J. ACM, 2017) and Nakar and Ron (ICALP, 2021), we initiate the study of property testing in dynamic environments with arbitrary topologies. Our focus is on the simplest non-trivial rule that can be tested,
Externí odkaz:
http://arxiv.org/abs/2309.05442
Autor:
Coiteux-Roy, Xavier, d'Amore, Francesco, Gajjala, Rishikesh, Kuhn, Fabian, Gall, François Le, Lievonen, Henrik, Modanese, Augusto, Renou, Marc-Olivier, Schmid, Gustav, Suomela, Jukka
We give an almost complete characterization of the hardness of $c$-coloring $\chi$-chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. In particular, we show that these problems do not admit any distribu
Externí odkaz:
http://arxiv.org/abs/2307.09444
Autor:
Modanese, Augusto
A sliding-window algorithm of window size $t$ is an algorithm whose current operation depends solely on the last $t$ symbols read. We construct pseudorandom generators (PRGs) for low-space randomized sliding-window algorithms that have access to a bi
Externí odkaz:
http://arxiv.org/abs/2301.07384
Autor:
Modanese, Augusto, Worsch, Thomas
Fungal automata are a variation of the two-dimensional sandpile automaton of Bak, Tang, and Wiesenfeld (Phys. Rev. Lett. 1987). In each step toppling cells emit grains only to some of their neighbors chosen according to a specific update sequence. We
Externí odkaz:
http://arxiv.org/abs/2208.08779
Autor:
Modanese, Augusto
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 cel
Externí odkaz:
http://arxiv.org/abs/2203.14614
Autor:
Modanese, Augusto
The minimum circuit size problem (MCSP) is a string compression problem with a parameter $s$ in which, given the truth table of a Boolean function over inputs of length $n$, one must answer whether it can be computed by a Boolean circuit of size at m
Externí odkaz:
http://arxiv.org/abs/2007.12048
Autor:
Modanese, Augusto
After an apparent hiatus of roughly 30 years, we revisit a seemingly neglected subject in the theory of (one-dimensional) cellular automata: sublinear-time computation. The model considered is that of ACAs, which are language acceptors whose acceptan
Externí odkaz:
http://arxiv.org/abs/1909.05828