4 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…