3 papers
cs.MA2024
The Geometry of Cyclical Social Trends
Bernard Chazelle, Kritkorn Karntikoon, Jakob Nogler
We investigate the emergence of periodic behavior in opinion dynamics and its underlying geometry. For this, we use a bounded-confidence model with contrarian agents in a convoluti…
cs.CC2023
2-Colorable Perfect Matching is NP-complete in 2-Connected 3-Regular Planar Graphs
Erik D. Demaine, Kritkorn Karntikoon, Nipun Pitimanaaree
The 2-colorable perfect matching problem asks whether a graph can be colored with two colors so that each node has exactly one neighbor with the same color as itself. We prove that…
cs.MA2022
Quick Relaxation in Collective Motion
Bernard Chazelle, Kritkorn Karntikoon
We establish sufficient conditions for the quick relaxation to kinetic equilibrium in the classic Vicsek-Cucker-Smale model of bird flocking. The convergence time is polynomial in…