Counting and hardness-of-finding fixed points in cellular automata on random graphs

About
Privacy
Disclaimer

Graph Chatbot

Related publications (4)

Page 1 of 1

Online Edge Coloring Is (Nearly) as Easy as Offline

Ola Nils Anders Svensson, Radu Vintan

The classic theorem of Vizing (Diskret. Analiz.'64) asserts that any graph of maximum degree Δcan be edge colored (offline) using no more than Γ+1 colors (with Δbeing a trivial lower bound). In the online setting, Bar-Noy, Motwani and Naor (IPL'92) conject ...

Association for Computing Machinery2024

How to Match in Modern Computational Settings

Buddhima Ruwanmini Gamlath Gamlath Ralalage

This thesis focuses on the maximum matching problem in modern computational settings where the algorithms have to make decisions with partial information. First, we consider two stochastic models called query-commit and price-of-information where the algo ...

EPFL2021

Heisenberg uncertainty principle as a probe of entanglement entropy: Application to superradiant quantum phase transitions

Pierre Marcel Nataf

Quantum phase transitions are often embodied by the critical behavior of purely quantum quantities such as entanglement or quantum fluctuations. In critical regions, we underline a general scaling relation between the entanglement entropy and one of the mo ...

Amer Physical Soc2012

Parity-regular Steinhaus graphs

Maxime Augier

Steinhaus graphs on n vertices are certain simple graphs in bijective correspondence with binary {0,1}-sequences of length n-1. A conjecture of Dymacek in 1979 states that the only nontrivial regular Steinhaus graphs are those corresponding to the periodic ...

American Mathematical Society2008