Computer Science/Discrete Mathematics Seminar I
Random Walk and Paint Blending
Random walks on a graph, and Markov chains in general, provide endless fascination and myriad applications (for example, in sampling and approximation algorithms.) A nearly trivial but endlessly useful tool in this theory is the "harmonic lemma for graphs". We show that the role of averaging in this lemma can be played by paint blending about which we know nothing.
Joint work with Tejo Madhavarapu and Kyle Petersen.
Date & Time
October 12, 2026 | 11:00am – 12:00pm
Add to calendar
10/12/2026 11:00
10/12/2026 12:00
Computer Science/Discrete Mathematics Seminar I
use-title
Topic: Random Walk and Paint Blending
Speakers: Peter Winkler, Dartmouth College
More: https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-seminar-i-632
Random walks on a graph, and Markov chains in general, provide endless
fascination and myriad applications (for example, in sampling and
approximation algorithms.) A nearly trivial but endlessly useful
tool in this theory is the "harmonic lemma for graphs". We show that
the role of averaging in this lemma can be played by paint blending
about which we know nothing.
Joint work with Tejo Madhavarapu and Kyle Petersen.
Simonyi 101 and Remote Access
a7a99c3d46944b65a08073518d638c23
Location
Simonyi 101 and Remote AccessSpeakers
Peter Winkler, Dartmouth College