camGates and Hillman Centers Photo Tour
School of Computer Science, carnegie Mellon
Computer Science Department
Human-Computer Interaction Inst
Institute for Software Research
Lane Ctr for Computational Biology
Language Technologies Institute
Machine Learning Department
Robotics Institute
Entertainment Technology Center
Extended Menu Contact Info Directory About SCS SCS New Buildings Info Giving to SCS SCS Dean's Advisory Board

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 Optimization

Phase 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