Behavioural Graph Colouring CS talk - Michael Kearns

Today, I attended a Computer Science talk by Michael Kearns about Behavioural Graph Colouring.

Abstract:
The pioneering work of Travers and Milgram in 1969 established the
now-familiar folklore of "six degrees" of separation in natural social
networks. More recently, researchers including Jon Kleinberg and Duncan
Watts have explored the algorithmic aspects of how messages are forwarded
in such networks. Perhaps the computer science view of this fascinating
line of thought can be best summarized as follows: Using relatively local
information, distributed human organizations can compute good
approximations to the all-pairs shortest paths problem. What other sorts
of distributed optimization problems can humans solve?

In this talk, I will first overview our more mathematical research at
the intersection of computer science, economics and social networks that
led us to be interested in the empirical question above. I will then
describe the preliminary findings of a behavioral study we held recently
at Penn. Human subjects attempted to perform distributed graph coloring
using a system that controlled network structure, information conditions,
and a variety of other variables of interest. The experiments shed early
light on whether such problems can be solved by humans, under what
conditions, and what algorithms they seem to adopt.

The behavioral experiments are joint work with Nick Montfort, Huanlei
Ni, and Siddharth Suri.

Bio:
Michael Kearns is a professor of Computer and Information
Science at the University of Pennsylvania, where he holds the National
Center Chair in Resource Management and Technology, and is co-director of
Penn's Institute for Research in Cognitive Science. He has published
extensively in the theory of machine learning, probabilistic artificial
intelligence, and related disciplines. His most recent interests lie at
the intersections of computer science with economics, game theory, and
finance.

This was an interesting talk, he talked about social network theory and how humans can collaborate to solve complex computer science problems, as shown from his preliminary results. It looks like social networks are being applied everywhere now, so it's good that my research is into this area and I switched professors in my PhD to continue along this line of research.