Events Calendar

GTHB Seminar

Speaker: Prof. Fan Chung Graham , Distinguished Professor of Mathematics, Distinguished Professor of Computer Science and Engineering,UCSD

Talk Title: Graph coloring games and memoryless voter models

Abstract: We analyze a network coloring game which can also describe a voter model. Each node represents a voter and is colored according to its preferred candidate, or undecided. Each hyperedge is a subset of nodes and can be viewed as a chat group. We consider interaction-based strategies involving chat groups: in each round of the game, one chat group is chosen randomly, and voters in the group can change colors based on informed discussion. We analyze the game as a random walk on the associated weighted directed state graph. Under certain `memoryless' conditions on the interaction strategies, the spectrum of the state graph can be explicitly determined and the random walk on the state graph converges to its stationary distribution in $O(m \log n)$ time, where $n$ denotes the number of voters and $m$ denotes the number of chat groups. This can then be used to determine the appropriate cut-off time for voting. For example, we show that the problem of estimating the probability that `blue' wins within an error bound of $\epsilon$ takes $O((\log 1/\epsilon) m \log n)$ rounds, provided the interaction strategies are memoryless.

This is a joint work with Alex Tsiatas and based on previous work with Ron Graham.


Biography: Fan Chung Graham received a B.S. degree in mathematics from National Taiwan University in 1970 and a Ph.D. in mathematics from the University of Pennsylvania in 1974, after which she joined the technical staff of AT&T Bell Laboratories. From 1983 to 1991, she headed the Mathematics, Information Sciences and Operations Research Division at Bellcore. In 1991 she became a Bellcore Fellow. In 1993, she was the Class of 1965 Professor of Mathematics at the the University of Pennsylvania. Since 1998, she has been a Professor of Mathematics and Professor of Computer Science and Enginering at the University of California, San Diego. She is also the Paul Erdos Professor in Combinatorics.

Her research interests are primarily in graph theory, combinatorics, and algorithmic design, in particular in spectral graph theory, extremal graphs, graph labeling, graph decompositions, random graphs, graph algorithms, parallel structures and various applications of graph theory in Internet computing, communication networks, software reliability, chemistry, engineering, and various areas of mathematics.
She was awarded the Allendoerfer Award by Mathematical Association of America in 1990. Since 1998, she has been a member of the American Academy of Arts and Sciences.

**Lunch served at 12pm. Talk begins at 12:10pm.
RSVP by Fri 1/7 to gthb-seminar@isi.edu.

Host: Prof. Milind Tambe, USC

Location: Seeley Wintersmith Mudd Memorial Hall (of Philosophy) (MHP) - 106

Audiences: Everyone Is Invited

Contact: Kanak Agrawal