Planted Distributions of Random Structures: an Introduction and One Problem Solved

ACO Student Seminar
Friday, February 17, 2012 - 13:00
1 hour (actually 50 minutes)
Skiles 005
Georgia Tech, School of Mathematics
I will define planted distributions of random structures and give plenty of examples in different contexts: from balls and bins, to random permutations, to random graphs and CSP's.  I will give an idea of how they are used and why they are interesting.  Then I'll focus on one particular problem: under what conditions can you distinguish a planted distribution from the standard distribution on a random structure and how can you do it?