Scribe notes on algorithms and complexities

Here are some notes I scribed for courses I take during the first year of my Ph.D. study. These notes have not been scrutinized as peer-reviewed works would have, and I am responsible for any mistakes within it.

• Continuous Optimization: Gradient Descent. This is a lecture from CS 787 Advanced Algorithms. We learned to show that gradient descent converges very fast on functions that are strongly convex and smooth.

• LP relaxation and rounding. This is a lecture from CS 880 Approximation and online algorithms. It is about the technique to approximate solutions for an integer linear program by relaxing the problem to linear program and solving the relaxed version of the problem.

• Random walk and hitting time. In CS 710 Computational Complexity, besides conventional materials from complexities, Prof. Jin-Yi Cai also gave us a taste of some beautiful results from random walks. This lecture a beautiful theorem not included in this scribe:

  Theorem(by Gobel and Jagers.) In any undirected connected graph \( G = (E,V) \), any two nodes \( i, j \in V\), two edges \({u, v}, {u’, v’} \in V \), \[\theta_{i,j,u,v} = \theta_{i,j,u’,v’},\] where \(\theta_{i,j,u,v}\) is the expected number of times that a random \( (i,j)\) commute traverses the edge \({u,v}\), and an \( (i,j)\) commute is a sequence of vertices that can be divided into two phases:

  • Phase 1: starting from vertex \(i\), ending with vertex \(j\), with no visits of \(j\) in between.
  • Phase 2: starting from vertex \(j\), ending with vertex \(j\), with no visits of \(i\) in between.

• Polynomial Hierarchy Theorem and Alternating Turing Machine.

• Chee Yap Theorem, Mahaney’s theorem, and Tail bound.

• Valiant-Vazirani Theorem and Efficient Amplification with Hashing mixing lemma. These three notes touch on cool theorems that show unobvious conditions that could render
  • \(\Sigma_2^P = \Pi_2^P \), see Polynomial Hierarchy Theorem;
  • or \(\Sigma_3^P = \Pi_3^P \), see Chee Yap Theorem.
  • or \(NP = P\): see Mahaney’s theorem.
  • or \(NP = RP \), randomized polynomial time : see Valiant-Vazirani Theorem.

(For the \(\Sigma\) and \(\Pi\) notations, I found Wikipedia page on polynomial hierarchy and this scribe helpful. )