75 citations
- Université Paris CitéFR78 papers
- Centre National de la Recherche ScientifiqueFR42 papers
- Délégation Paris 7FR14 papers
- Institut national de recherche en sciences et technologies du numériqueFR14 papers
- Laboratoire Bordelais de Recherche en InformatiqueFR11 papers
- Sorbonne UniversitéFR6 papers
- Laboratoire d'Informatique de l'École PolytechniqueFR5 papers
- École Normale Supérieure de LyonFR4 papers
- Computer Algorithms for MedicineAT3 papers
- École Normale Supérieure - PSLFR3 papers
- École PolytechniqueFR3 papers
- Laboratoire de Recherche en InformatiqueFR3 papers
10 papers · 1 filter
Convergence to Equilibrium of Logit Dynamics for Strategic Games
Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale +2
We present the first general bounds on the mixing time of the Markov chain associated to the logit dynamics for wide classes of strategic games. The logit dynamics with inverse noi…
From Bi-immunity to Absolute Undecidability
Laurent Bienvenu, Rupert Hölzl, Adam R. Day
An infinite binary sequence A is absolutely undecidable if it is impossible to compute A on a set of positions of positive upper density. Absolute undecidability is a weakening of…
Probabilistic cellular automata and random fields with i.i.d. directions
Jean Mairesse, Irene Marcovici
Let us consider the simplest model of one-dimensional probabilistic cellular automata (PCA). The cells are indexed by the integers, the alphabet is {0, 1}, and all the cells evolve…
On digit patterns in expansions of rational numbers with prime denominator
Igor E. Shparlinski, Wolfgang Steiner
We show that, for any fixed and almost all primes , the -ary expansion of any fraction with contains almost all -ary strings of len…
Multiple Petersen subdivisions in permutation graphs
Tomáš Kaiser, Jean-Sébastien Sereni, Zelealem Yilma
A permutation graph is a cubic graph admitting a 1-factor M whose complement consists of two chordless cycles. Extending results of Ellingham and of Goldwasser and Zhang, we prove…
A new bound for the 2/3 conjecture
Daniel Král', Chun-Hung Liu, Jean-Sébastien Sereni +2
We show that any n-vertex complete graph with edges colored with three colors contains a set of at most four vertices such that the number of the neighbors of these vertices in one…