Welcome to Randomized Algorithms! Class meets on Mondays and Wednesdays at 12:30 - 1:45pm in Phelps 1440.

Eric's Office Hours: Mondays and Wednesdays: 2:30-3:15pm in Eric's office (HFH 2113)

Ed Discussion: Sign up here:

Optional textbook: Probability and Computing by Michael Mitzenmacher and Eli Upfal [MU], see:
Amazon and Library (this is the older version, unfortunately even that doesn't seem to be available at UCSB).

Grading scheme:

Homeworks: 50% (out: Mondays, due: following Monday night)
Final project: 30%
Class participation: 20%

----------------------------------

Lecture schedule:

Eric's handwritten notes will be posted in Files section.

Monday, June 5th: Random Matchings
Wednesday, June 7th: Permanent: Random Perfect Matchings of Bipartite Graphs

Wednesday, May 31st: Conductance and Canonical Paths

Monday, May 22nd: Random spanning trees
Wednesday, May 24th: Matrix-Tree Theorem: Exact counting of spanning trees

Monday, May 15th: Glauber dynamics for colorings, Path Coupling
Wednesday, May 17th: Coupling from the Past
Reading: [Mitz-Upfal] Chapters 12.5-12.6

Monday, May 8th: Markov chain basics: Stationary distribution, ergodic MC
Wednesday, May 10th: Mixing Time, Coupling
Reading: [Mitz-Upfal] Chapters 11.4 and 12.1-12.2

Monday, May 1st: Data Streaming: Median estimation and random sampling
Wednesday, May 3rd: More streaming: Number of unique elements
Reading: Amit Chakrabarti's Dartmouth notes

Monday, April 24th: Class cancelled (Eric's jury duty)
Wednesday, April 26th: Chernoff bounds
Reading: [Mitz-Upfal] Chapters 4.1-4.2

Monday, April 17th: Randomized QuickSort and QuickSelect -- Expected run time
Deterministic Median in linear time (Eric's lecture notes)
Wednesday, April 19th: Randomized Median in linear time with high prob. via Variance analysis
Reading: [Mitz-Upfal] Chapter 3.5

Monday, April 10th: Max-SAT, 1/2-approximation algorithm via method of conditional expectations
Wednesday, April 12th: 3/4-approx via LP rounding   (Eric's old lecture notes)
      Reading: For an intro to Linear Programming (LP) check out LP video from Eric's MOOC or Chapter 7 of Algorithms by [DPV].
      HW 2 is posted on Gradescope: Due Wednesday, April 19th

Monday, April 3rd: Karger's Min-cut Algorithm
Wednesday, April 5th: Faster Karger-Stein's Min-cut algorithm and Coupon Collector's problem
Reading: [MU] Chapter 1.5 or Eric's old lecture notes
HW 1 is posted on Gradescope: Due Wednesday, April 12th

Project ideas (possible research papers to read):

Cover Time: O(nm) bound by [Aleliunas, Karp, Lipton, Lovasz, Rackoff '79], see: https://www2.eecs.berkeley.edu/Pubs/TechRpts/1979/ERL-m-79-54.pdf
or improved bound for regular graphs, see: https://link.springer.com/article/10.1007/BF01048274
Balanced Allocation Through Random Walk (Cuckoo hashing) by Frieze and Petti: https://arxiv.org/pdf/1708.04945.pdf
Why Simple Hash Functions Work (Bloom filters with limited independence) by Mitzenmacher and Vadhan, see: https://www.eecs.harvard.edu/~michaelm/postscripts/soda2008b.pdf
Balls and Bins: A Study in Negative Dependence by Dubhashi and Ranjan, see: https://onlinelibrary-wiley-com.proxy.library.ucsb.edu/doi/pdfdirect/10.1002/(SICI)1098-2418(199809)13%3A2%3C99%3A%3AAID-RSA1%3E3.0.CO%3B2-M
Improved Approximation Algorithms for Max Cut using Semidefinite Programming by Goemans and Williamson, see: https://math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf
Estimating PageRank on Graph Streams by Das Sarma, Gollapudi, and Panigrahy, see: https://theory.stanford.edu/~rinap/papers/pagerankpods.pdf
Counting Distinct Elements in a Data Stream by Bar-Yossef, Jayram, Kumar, Sivakumar, and Trevisan, see: https://cs.haifa.ac.il/~ilan/randomized_algorithms/bar-yosef_jayram.pdf
Learning Mixtures of Gaussians (Dimension reduction by random projection) by Dasgupta, see: https://cseweb.ucsd.edu/~dasgupta/papers/mog.pdf
Random Walk Algorithm for Random 3-SAT by Alekhnovich and Ben-Sasson, see: https://www.cs.cornell.edu/selman/docs/eli-02.pdf
Power of 2 choices: Always go left by Vocking, see: https://faculty.cc.gatech.edu/~vigoda/RandAlgs/Vocking.pdf
Improved bounds for random colorings (Vigoda's improvement of 2D --> (11/6)D), see: https://www.math.cmu.edu/~af1p/Teaching/MCC17/Papers/color116.pdf

Project ideas (possible simulations to pursue):

Colorings: Generate a random D-regular bipartite graph on 2n vertices (do this by generating D random permutations and ignoring the multiplicity of edges so the resulting graph is max degree D, not necessarily D-regular). Then run the Glauber dynamics to try to test convergence as a function of k/D. When does it appear to slow down? Then try doing a flip dynamics so flip maximal 2-colored components in each step; when does this Markov chain appear to slow down?
Independent Sets: Run the Glauber dynamics for independent sets weighted by a parameter \lambda>0 so the weight of an independent set is \lambda^{|S|}. Run it on an nxn grid (with periodic boundary, so wrap around). Increase \lambda and test convergence. The proposed critical point is \lambda_c approx 3.79. Does the Glauber dynamics appear to slow down at that critical point or earlier?
Ising/Potts: Run the Glauber dynamics for the Ising model (q=2) and Potts model (q=3,4,5,6) on an nxn grid (with periodic boundary, so wrap around). Start with small \beta and increase \beta, testing convergence by the identity coupling. Does it slow down at the critical point or earlier? For different q, can you test at the critical point to see the convergence time as a function of n?