6 papers
The -Energy and Its Applications
Bernard Chazelle, Kritkorn Karntikoon
Many multi-agent systems evolve by repeatedly updating each state to a weighted average of its neighbors, a process known as averaging dynamics, whose behavior becomes difficult to…
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…
First Passage Percolation with Queried Hints
Kritkorn Karntikoon, Yiheng Shen, Sreenivas Gollapudi +3
Solving optimization problems leads to elegant and practical solutions in a wide variety of real-world applications. In many of those real-world applications, some of the informati…
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…
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…
Unfolding Orthotubes with a Dual Hamiltonian Path
Erik D. Demaine, Kritkorn Karntikoon
An orthotube consists of orthogonal boxes (e.g., unit cubes) glued face-to-face to form a path. In 1998, Biedl et al. showed that every orthotube has a grid unfolding: a cutting al…