16 citations · 46 across the 31 of their papers we have counts for
Showing 2023Show all
2 papers · 1 filter
cs.DC2023
Local Certification of Majority Dynamics
Diego Maldonado, Pedro Montealegre, Martín Ríos-Wilson +1
In majority voting dynamics, a group of agents in a social network are asked for their preferred candidate in a future election between two possible choices. At each time step,…
cs.CC2023
Hardness of monadic second-order formulae over succinct graphs
Guilhem Gamard, Aliénor Goubault-Larrecq, Pierre Guillon +3
Our main result is a succinct counterpoint to Courcelle's meta-theorem as follows: every cw-nontrivial monadic second-order (MSO) property is either NP-hard or coNP-hard over graph…