Prof. Tim Roughgraden - SPECIAL DISTINGUISHED LECTURE - note unusual date
יום חמישי, 7.2.2019, 14:30
The mathematical study of social and information networks has
historically centered around generative models for such networks
(preferential attachment, the Chung-Lu random graph model, Kronecker
graphs, etc.). This talk proposes distribution-free models of social and
information networks - novel classes of graphs that capture all
plausible such networks. Our models are motivated by triadic closure,
the property that vertices with one or more mutual neighbors tend to
also be neighbors; this is one of the most universal signatures of
social networks. We prove structural results on the clustering
properties of such graphs, and give algorithmic applications to
clustering and clique-finding problems.
Includes joint work with Jacob Fox, Rishi Gupta, C. Seshadhri, Fan Wei,
and Nicole Wein.
Tim Roughgarden is a Professor of Computer Science at Columbia University.
Prior to joining Columbia, he spent 15 years on the Computer Science Faculty
at Stanford, following a PhD at Cornell and a postdoc at UC Berkeley. His
research interests include the many connections between computer science and
economics, as well as the design, analysis, applications, and limitations
of algorithms. For his research, he has been awarded the ACM Grace Murray
Hopper Award, the Presidential Early Career Award for Scientists and Engineers
(PECASE), the Kalai Prize in Computer Science and Game Theory, the Social
Choice and Welfare Prize, the Mathematical Programming Society's Tucker Prize,
and the EATCS-SIGACT Goedel Prize. He was an invited speaker at the 2006
International Congress of Mathematicians, the Shapley Lecturer at the
2008 World Congress of the Game Theory Society, and a Guggenheim Fellow
in 2017. His books include Twenty Lectures on Algorithmic Game Theory
(2016) and the Algorithms Illuminated book series (2017-2019).
Refreshments will be served from 14:15
Lecture starts at 14:30