Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Algorithms, Combinatorics and Optimization Seminar
For more information, please visit the home page for the program in Algorithms, Combinatorics and Optimization at Carnegie Mellon University. Carnegie Mellon University offers an interdisciplinary Ph.D program in Algorithms, Combinatorics and Optimization. This program is the first of its kind in the United States. It is administered jointly by the Tepper School of Business (Operations Research group), the Computer Science Department (Algorithms and Complexity group) and the Department of Mathematical Sciences (Discrete Mathematics group). (Learn more...) Michael Krivelevich Tel Aviv University Title: Smoothed analysis on connected graphs Abstract: The main paradigm of smoothed analysis on graphs suggests that for any large graph G in a certain class of graphs, perturbing slightly the edges of G at random (usually adding few random edges to G) typically results in a graph having much nicer properties.In this talk we discuss smoothed analysis on trees, or equivalently on connected graphs. A connected graph - its edge expansion is at least
*c*/log*n*; - its diameter is
*O*(log*n*); - its vertex expansion is at least
*c*/log*n*; - it has a linearly long path;
- its mixing time is
*O*(log^{2}*n*)
G has bounded degrees). All of the above estimates are asymptotically tight.Joint work with Daniel Reichman (Weizmann Institute) and Wojciech Samotij (Tel Aviv/Cambridge). |