Selected topics in computational complexity II (NTIN086)
The lecture takes place every Tuesday at 2 pm in the corridor at the 3rd floor (code S321).
E-mail: josef.tkadlec (AT) iuuk.mff.cuni.cz
Syllabus
In this semester, we will focus on Evolutionary graph theory -- the field which studies random processes that model how entities (such as opinions, viruses, or genetic mutations) propagate through network-structured populations. Along the way we introduce notions such as Markov chains or martingales and we answer questions such as "How long does it take until a randomly typing monkey types a word 'abracadabra'?" We assume basic knowledge of discrete mathematics and probability.
Credit requirement:
Get at least 80 points out of at least 120 points available for homework assignments.
Please submit the assignments in the Postal Owl. Use token e7ea045609e2. The assignment is typically due in 12 days (on Sunday next week).
Assignment 1 (due on Friday, Feb 23): PDF
Assignment 2 (due on Friday, March 8): PDF
Assignment 3 (due on Sunday, March 24): PDF
Assignment 4 (due on Sunday, April 7): PDF
Assignment 5 (due on Sunday, April 21): PDF
Assignment 6 (due on Sunday, May 5): PDF
Assignment 7 (due on Sunday, May 19): PDF
Exam format:
Written part with at most 5 questions ("define X", "state Y", "write what you know about Z", "solve the following problem"), then an oral part. Content: everything that we covered, except for the final lecture (May 21).
Content:
Feb 20, 2024: No lecture. Instead, please read the following 6 problems (PDF) and comment on them in the Postal Owl by Friday, Feb 23.
Feb 27, 2024: Assignment solutions. Linearity of expectation. Coupon collector's problem. Buffon needle / noodle.
Mar 05, 2024: Solution to Problem 5b from Assignment 1. Expected number of rolls until you hit or exceed 100. Greedily guessing cards A, 2, 3, 4. Eating chocolate. Chip-firing games on graphs.
Mar 12, 2024: Solutions to Problems 2, 3 from Assignment 2. O(n^4) bound for chip-firing. Conway's soldiers (and the app). Polya's urn: Expected proportion of red balls is preserved.
Mar 19, 2024: Expected time until a binary pattern appears (by solving a linear system). Sketches of formal definitions of a stochastic process and a martingale. Polya's Urn revisited (when stopping at 2 blue balls, E[#red balls] is infinite, but E[proportion of red balls] finite). Abracadabra problem. Penney's game (Conway's algorithm just mentioned).
Mar 26, 2024: Solution to Problem 1 from Assignment 3. Efron's dice. Hat problems: Two people, N people with passing allowed, 2 people with 100 hats each (see also Theorem 1 here).
Apr 2, 2024: Random walk on a line. With absorbing boundaries: absorption probability is i/n, expected absorption time is i(n-i). On an infinite line: After n steps you are \sqrt{n} away; probability of staying positive is \Theta(1/\sqrt{n}) (André's reflection method). With constant forward bias: probability of staying positive is 1-1/r (by algebra, or by the exponential potential); E[#visits]=(r+1)/(r-1). Wolf and sheep puzzle.
Apr 9, 2024: Random walk on a graph (see e.g. here). Stationary distribution is proportional to degree. Return time is inversely proportional to the degree. Example: knight walk on a chessboard. Cover time. Cover time on K_n is \Theta(n\log n). Cover time on P_{n+1} is n^2. In a random walk, each edge is used equally often. Cover time on any (undirected) G_n is O(n^3).
Apr 16, 2024: Tennis serving schemes problem. Wolf and sheep revisited. Broder algorithm for u.a.r. spanning tree (no proof). Loop-erased random walk. Wilson algorithm for u.a.r. spanning tree. Moran process on a graph, fixation probability, absorption time. fp_r(K_n)=(1-1/r)/(1-1/r^n).
Apr 23, 2024: Wilson algorithm revisited. Moran process on specific graphs, namely: Complete graph: AT_r(K_n)=O(n\log n). Cycle graph: AT_r(C_n)=O(n^2). Isothermal theorem: fp_r(R_n)=fp_r(K_n) for any regular graph. Star graph: fp_r(S_n,leaf)\approx 1-1/r^2 (Monk et al, '14). Intuition for AT_r(S_n,leaf)= \Theta(n^2\log n). Probability-time landscape of undirected graphs for n=8 and r=1.1 (fig).
Apr 30, 2024: Asymptotic probability-time landscape of Moran process on undirected graphs with $r>1$: Lower bound on time AT_r(G_n)=\Omega(n\log n) [TPCN '18]. Upper bound on time AT_r(G_n)=O(n^4) [DGMRSS '14]. Stronger upper bound AT_r(G_n)=O(n^{3+\eps) just mentioned. AT_r(D_n)=\Omega(n^3) [GLR '20]. Exponentially slow directed graphs just mentioned [DGRS '16]. General argument "E[#steps]<T implies P[#steps>T*3log n]<1/n^3". Strong suppressors [G '16]. Strong amplifiers just mentioned [GLLMPP '19].
May 7, 2024: Moran process wrap-up (approximating fp on directed graphs is open). Black spread problem. Pollak's parking problem. Boarding an airplane. Cycles in random permutations (P[1..k are in one cycle]=1/k, P[1 is in a k-cycle]=1/n). 100 prisoners problem (just strategy+answer, no proof).
May 14, 2024: No lecture (Rector's day).
May 21, 2024: Cool solution to "Stop, I think the next card is red" from the homework assignment. Problems around random points on a segment, circle and a sphere (see the notes).