Clark School Home UMD

ISR Events Calendar

Event Information

Computer Science Distinguished Colloquium: Alan Frieze, "Topics in Markov Chains"
Friday, October 5, 2018
11:00 a.m.
2117 CSIC
For More Information:

Topics in Markov Chains

Alan Frieze
Professor of Mathematical Sciences
Carnegie Mellon University

Friday, October 5th 2018 11:00am CSIC 2117 Abstract: We give some examples on problems related to finite state Markov chains. Gerrymandering: There are many ways to choose a set of political districts. Let Ω denote the set of possible districtings. Some ω ∈ Ω are more favorable than others to one party. Fairness might dictate that one should try to select (near) uniformly from Ω. If one is presented with ω ∈ Ω, how does one determine whether it is likely that it has been chosen uniformly? We present a one sided test that will recognise when a presented ω is an outlier. It was used in a recent court case in Pennsylvania. Sampling and Counting: Markov chains “typically” have steady state distributions and can thus be used to generate samples from this distribution, provided the “mixing time” is small. Broder pioneered this approach in Computer Science in the context of approximating the permanent. We will do a mini-survey on this area. Cover Time: The cover time of a graph G is the maximum over vertices v ∈ V (G) of the expected time for a simple random walk to visit all vertices ofG, starting at v. We will review what we know about this question and present asymptotic characterizations of the cover time in a few regimes. Various parts of this talk are joint works with subsets of Colin Cooper, Wesley Pegden, and Tomasz Tkocz. Biography: Alan Frieze is a Professor of Mathematical Sciences at Carnegie-Mellon University; he was named a University Professor of CMU in 2017. His main research interest is Probabilistic Combinatorics and its applications in Theoretical Computer Science and Operations Research. He received a Fulkerson Prize in Discrete Mathematics (awarded by the American Mathematical Society and the Mathematical Programming Society), a Guggenheim Fellowship, an IBM Faculty Partnership Award, and a Professor Pazy Memorial Research Award (from the United States-Israel Binational Science Foundation). He is a SIAM Fellow, AMS Fellow, and Simons Fellow. He delivered a plenary talk at the International Congress of Mathematicians in 2014.

This Event is For: Graduate • Undergraduate • Faculty • Post-Docs

Browse Events By Calendar

Calendar Home

« Previous Month    Next Month »

September 2019
SU M TU W TH F SA
1 2 3 4 5 6 7 w
8 9 10 11 12 13 14 w
15 16 17 18 19 20 21 w
22 23 24 25 26 27 28 w
29 30 w

Search Events


ISR lecture and seminar series

Distinguished Lecturer Series
Intelligent Automation Inc. Colloquia Series
Microsystems Seminar Series
Lockheed Martin Robotics Seminar Series
Advanced Networks Colloquia Series
Model-Based Systems Engineering Colloquia Series

Submit an event to the ISR calendar Click here

News links

Current news
Search news
News archives