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.

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).