1. Aggregating Inconsistent Information: Ranking and Clustering
This paper has a lot, but in it is a very cute algorithm using ideas from QuickSort to convert a tournament (a directed graph on n-vertices where for every pair of vertices u and v either the (u,v) or the (v,u) edge is present but not both) into a DAG. Which in turn has applications in rank aggregation.

Suggested Sections: 1, 2, 3 & (maybe, if interested) 5. [Chosen by Themistoklis Haris]

2. Karger-Stein Algorithm.
As mentioned in class, Karger's minimum cut algorithm doesn't give the best running time. However, the ideas there can give a faster minimum cut algorithm. Read and understand this algorithm (the textbook, sec 10.2). Then think how you will give an one-hour lecture, write lecture notes (~ 3-4 pages). [Chosen by Yitong Deng and Jinyuan Liu]

3. Benczur-Karger Algorithm.
Another fascinating outcome of the Randomized Contraction Algorithm is the following sparsification theorem. It says the following: given any undirected multigraph G on n vertices, one can construct another weighted graph H on n vertices with only O(\frac{n \log n}{\varepsilon^2}) edges, such that for every subset S\subseteq V, the following is true : the weight of the cut S in H is within (1 \pm \varepsilon) of the cut value of S in G. Note that the original graph G can have \Theta(n^2) edges. The sparsification statement says that all the cuts can be approximate preserved in a much sparser graph.

Suggested Sections: 1, 2, and maybe 4

4. Karp-Luby-Madras for counting #DNF
In class, we saw an algorithm which gave an unbiased estimate in O(mn) time, where m is the number of clauses and n is the number of variables. The variance was <= m. Then, median-of-means gave the desired result. This algorithm is via Karp and Luby. In this journal version, there is a second estimate which is slicker and saves an m from the total running time. In this reading/writing project, your goal is to understand this algorithm and write 2-3 pages about it. I am imagining it as supplementing the Lecture 7 notes. [Chosen by Abigail Bartolome]

5. Path Sampling for Subgraph Counting
Estimating the number of small subgraphs in a huge is an important problem in data mining. This paper focusses on counting subgraphs on 4 vertices. Their ideas are similar to the importance sampling idea a la Cohen and Lewis. I think there is enough material to create a nice one hour lecture (3-4 pages). You can choose which part appeals to you the most. [Chosen by Sayak Chakrabarty]

6. A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
In this paper, the authors assume that one has random access to an edge in a graph. With this power, they are able to obtain a generic result for counting the number of arbitrary subgraphs in a graph. It would ne nice to understand what this paper does for say triangles or 4-cycles and present that result.

7. A Space Efficient Streaming Algorithm for Triangle Counting using the Birthday Paradox
This data mining paper has an estimation algorithm for counting triangles "on the fly". This is a model in which edges arrive at you but your algorithm has only limited memory. This paper seems to combine ideas from estimation and birthday paradox style collisions, to get an algorithm. [Chosen by Hang Liao]

8. An Optimal Decentralized (Δ + 1)-Coloring Algorithm
This paper solves a generalization of the coupon collector problem I mentioned in class. The model is where each router (node) chooses a channel (color) at random. How long does it take to get to a "stable" solution if the number of channels is >= max-degree + 1. Turns out the answer is O(n log max-degree), which generalizes Coupon Collector. [Chosen by Ankita Sarkar]

9. Closest Points using Hashing.
In undergraduate algorithms, we see an O(n log n) time divide-and-conquer algorithm to find the nearest points on the plane. Using hashing, there is an O(n) expected time algorithm possible. This generalizes to higher dimensions as well. [Chosen by So Amano]

10. Wegman-Carter Hash Functions.
In class, we saw the Carter-Wegman hash functions which took $LaTeX: x\mapsto ((ax+b)\bmod p)\bmod n$ where, recall, p was a prime bigger than the universe size. Therefore, the "size" of the function (#of bits used to describe a,b,p) was roughly $LaTeX: O(\log |U|)$ bits. In particular, if U consisted of s-bit strings, then the size of the hash function was O(s). The same authors, in the above paper, describe a scheme where each function description requires $LaTeX: O(\log s)$ bits. However, it is only "almost" universal. Your goal will be to clearly present the hash family, and then prove why it is almost universal. Most of this is in Section 3. [Chosen by Yang Qi]

11. Degree Sequence Estimations in Multigraph Streams.
In this paper, the authors look at the scenario where edges of a multi-graph stream in, but they are interested in the properties of the underlying simple graph. That is, the graph with all parallel edges removed. In particular, they are interested in estimating the degrees of the simple graph, or the underlying degree moments, etc. One could look at the "M2 estimation", or the sum of squares of degree estimation, as a nice reading/writing project. [Chosen by Fan Feng and Mengdi Wang]