Finitely Dependent Coloring

Channel:
Microsoft Research
Subscribers:
351,000
Published on ● Video Link: https://www.youtube.com/watch?v=qCLGVK9pZ70


Duration: 41:42
80 views
1

Do local constraints demand global coordination? I'll address a particularly simple formulation of this question: can the vertices of a graph be assigned random colours in a stationary way, so that neighboring colours always differ, but without long-range dependence? The quest to answer this has led to the discovery of a beautiful yet mysterious new stochastic process that seemingly has no right to exist, while overturning the conventional thinking on a fundamental 49-year old question. (Joint work with Tom Liggett.)



Other Videos By Microsoft Research


2016-06-21Theory Day Session 2
2016-06-21Modular Total Correctness Verification of Fine-Grained Concurrent Programs with Exceptions and I/O
2016-06-21MSR NYC Data Science Seminar Series #2
2016-06-21MSR Theory Day - Part 3
2016-06-21Engineering Serendipity
2016-06-21Operationalizing Predictive Model
2016-06-21Theory Day Session 1
2016-06-21On understanding types, data abstraction and effects
2016-06-21Interdisciplinarity: A View from Theoretical Computer Science
2016-06-21Automorphisms of Graphons
2016-06-21Finitely Dependent Coloring
2016-06-21Squared Distance Matrix of a Tree
2016-06-21Near Future Laboratory
2016-06-21Luca Cardelli and the Early Evolution of ML
2016-06-21How abstract should abstract types be?
2016-06-21Deadlock analysis of unbounded process networks
2016-06-21Full reduction in the face of absurdity
2016-06-21A Brief Introduction to Microsoft Research
2016-06-21Networked Publics as Third Places
2016-06-21Using a Push-Button Verifying Compiler to Build Verified Software Components
2016-06-21Challenges in Geo-Distributed Data Center and Application Design


Tags:
microsoft research