research
∙
09/11/2023
Testing Spreading Behavior in Networks with Arbitrary Topologies
Inspired by the works of Goldreich and Ron (J. ACM, 2017) and Nakar and ...
share
research
∙
07/18/2023
No distributed quantum advantage for approximate graph coloring
We give an almost complete characterization of the hardness of c-colorin...
research
∙
01/18/2023
Pseudorandom Generators for Sliding-Window Algorithms
A sliding-window algorithm of window size t is an algorithm whose curren...
research
∙
08/18/2022
Embedding arbitrary Boolean circuits into fungal automata
Fungal automata are a variation of the two-dimensional sandpile automato...
research
∙
03/28/2022
Sublinear-Time Probabilistic Cellular Automata
We propose and investigate a probabilistic model of sublinear-time one-d...
research
∙
07/23/2020
Lower Bounds and Hardness Magnification for Sublinear-Time Shrinking Cellular Automata
The minimum circuit size problem (MCSP) is a string compression problem ...
research
∙
09/12/2019
Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata
After an apparent hiatus of roughly 30 years, we revisit a seemingly neg...
research
∙
02/14/2019