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 networks solve?

In this talk, I will describe the preliminary but thought-provoking findings of a series of behavioral experiments we have been performing at Penn. Human subjects attempt to perform distributed graph coloring using a system that controls network structure, information conditions, incentives, and a variety of other variables of interest. The experiments shed early light on whether such problems can be solved by human networks, under what conditions, and what algorithms they seem to adopt.

Short Bio: I am a professor in the Computer and Information Science Department at the University of Pennsylvania, where I hold the National Center Chair in Resource Management and Technology.

I am also the head of quantitative strategy development in the Equity Strategies department of Lehman Brothers in New York City. (Please send any Lehman-related email to mkearns@lehman.com.)

At Penn, I am the co-director (with Linguistics professor Mark Liberman) of Penn's interdisciplinary Institute for Research in Cognitive Science. I also have a secondary appointment in the Operations and Information Management (OPIM) department of the Wharton School. In 2001, I took a brief sabbatical from pure research as Chief Technology Officer of Syntek Capital.

I spent the decade 1991-2001 in basic AI and machine learning research at AT&T Labs and Bell Labs. During my last four years there, I was the head of the AI department, which conducted a broad range of systems and foundational AI work. During my time at AT&T/Bell Labs, I also served as the head of the Machine Learning department, and as the head of the Secure Systems Research department.

I joined the Penn faculty in January 2002.