|  |
SCS DISTINGUISHED LECTURE SERIES
4:00 PM - Wean Hall 7500
3:45 PM Distinguished Donuts - Outside the Hall
Annual Women@SCS Distinguished Lecture

Jennifer Tour Chayes
Co-Founder and Co-Manager, The Theory Group, Microsoft Research
Phase Transitions in Combinatorial OptimizationPhase transitions are familiar phenomena in physical systems.
But they also occur in random versions of combinatorial models,
including random versions of some of the canonical problems of
theoretical computer science. In this talk, I will illustrate this by
discussing joint work with Christian Borgs, Stephan Mertens and Boris
Pittel on the so-called random optimum partitioning or load balancing
problem -- a fundamental problem in combinatorial optimization. I will
show how this problem undergoes a phase transition from a phase in which
it is typically possible to balance loads to a phase in which such
balance cannot be achieved. I will also discuss how notions of phase
transitions may help us to understand what makes hard problems hard,
with possible implications for complexity theory and possible
applications in cryptograpy. No previous knowledge of phase transitions
will be assumed in this talk.Speaker Bio: Jennifer Tour Chayes is a world expert in the emerging field at
the interface of mathematics, physics, and theoretical computer
science. She is Co-Founder and Co-Manager of the Theory Group at
Microsoft Research. Chayes is also Affiliate Professor of
Mathematics and Physics at the University of Washington, and
was for many years Professor of Mathematics at UCLA. She is the
recipient of a National Science Foundation Postdoctoral Fellowship,
a Sloan Fellowship, and the UCLA Distinguished Teaching Award.
Chayes serves on numerous institute boards, advisory committees
and editorial boards, including the Scientific Boards of the Banff
International Research Station, and the Fields Institute, the
Advisory Boards of the Center for Discrete Mathematics and Computer
Science, and the National Academy of Sciences' Office on the
Public Understanding of Science, and the U.S. National Committee
for Mathematics. Chayes is Chair of the Mathematics Section of the
American Association for the Advancement of Science, and is a
past Vice-President of the American Mathematical Society.
Chayes received her B.A. in biology and physics at Wesleyan
University, where she graduated first in her class, and her Ph.D.
in mathematical physics at Princeton. She did her postdoctoral
work in the mathematics and physics departments at Harvard and
Cornell. Chayes has twice been a member of the Institute for
Advanced Study in Princeton. She lives in Seattle with her husband,
Christian Borgs, with whom she co-manages the Theory Group. In her
spare time, Chayes enjoys overworking.
<< Back
|