Social Balance

“The shifting of alliances and rivalries in a social group can be viewed as arising from an energy minimization process. For example, suppose you have two friends who happen to detest each other. The resulting awkwardness often resolves itself in one of two ways: either you drop one of your friends, or they find a way to reconcile. In such scenarios, the overall social stress corresponds to a kind of energy that relaxes over time as relationships switch from hostility to friendship or vice versa.” — from Energy Landscape of Social Balance, Seth A. Marvel, Steven H. Strogatz, and Jon M. Kleinberg, DOI: 10.1103/PhysRevLett.103.198701

Very interesting! More interesting is what they conclude for the future research, viz, the “challenge for the future is to understand its large-scale structure, perhaps even including a characterization of the pathways leading out of the deepest minima–those corresponding to the most entrenched conflict–and toward states of reconciliation.”

CS Trees: A Graph Theory Joke

Most trees you’ll see in Computer Science literature are rooted on top and spread downwards. Why do CS folks call them tree then? Well, common wisdom is that they never went out of the room, so they never saw a real tree. 😀

No offense. I am a CS theory guy myself. I read this joke a long time back, when I was tutoring an undergraduate class, in this book. A group of theorists was discussing some open problems, that could be trivial (but nobody could see the triviality) to solve, and the joke was mentioned. Open problems that could be trivially settled?! Some kind of tomfoolery! Well, not going out of their rooms might just be true..Not seeing a real tree is not. 😉

Algorithmic Combinatorial Game Theory

Prof. Erik Demaine has updated the survey paper titled “Playing Games with Algorithms: Algorithmic Combinatorial Game Theory.” The recent update appears after a long wait of 7 years and has Prof. Bob Hearn as a coauthor.

The paper presents interesting, clean problems in algorithms and complexity theory –many of which remain open– with the purpose to provide an overview of the area to encourage further research.