Instructor: Hemanshu Kaul

Office: 238, M.E.B. (and 178, Altgeld Hall)
Phone: 217-244 0292 (office)
E-mail: hkaul [at] math [dot] uiuc [dot] edu

Time: 4pm, Monday and Wednesday (occasionally, 4pm Friday)
Place: 241, Altgeld Hall

Course Information: A detailed description of the lecture topics is available in the course proposal .
In brief, the lectures will discuss three areas and their applications that are not well covered in other graduate courses: Concentration of Measure (large deviation inequalities), Applications of Entropy, and Rapidly Mixing Markov Chains (Markov Chain Monte Carlo). The lectures will present elementary proofs of basic results in these areas. The focus will be on developing the themes underlying the various methods and illustrating the final results through applications in graph theory, combinatorial optimization and theoretical computer science. Some past exposure to probability or probabilistic methods will be helpful.

• Wednesday, 8/24 : The first class will be held on Friday (8/26), followed by the usual Monday-Wednesday schedule from next week.
• Wednesday, 8/31 : Next week, due to Labor day holiday, the classes will be held on Wednesday (9/7) and Friday (9/9), followed by the usual Monday-Wednesday schedule.
• Friday, 9/16 : No class on Monday (9/19) due to the Trjitzinsky Memorial Lecture by Jean Bourgain.
  Class on Wednesday (9/21) as usual. Followed by classes on Monday (9/26), Wednesday (9/28), and Friday (9/20).
• Wednesday, 10/12 : Extra class on Friday (10/14) to make-up for the class on Monday (10/17).
  No class on Monday (10/17) due to seminar by Prof. Jozsef Balogh.
• Wednesday, 10/19 : We have an extra class on Friday, 10/21.
• Wednesday, 10/26 : We will start with a new topic - Markov Chain Monte Carlo - on Monday, 10/31.
• Wednesday, 11/9 : We will prove our first explicit bound on the mixing time of a MCMC in the next class on Monday, 11/28. See below for details.
  Over the last six classes we will do as many examples as possible for applications of the four main methods (coupling, path coupling, 'flow congestion', conductance) for bounding mixing times of MCMCs.

• Friday, 8/26 : [make-up class for 8/24] Outline of the topics to be covered in Concentration of Measure; (first) discussion of "what is the concentration of measure phenomenon?"; method of exponential generating function leading to Chernoff-Hoeffding bounds and various generalizations.
• Monday, 8/29 : applications of C-H bounds to Combinatorial Discrepancy (also, comparison with Chebyshev's inequality) and Discrete Geometry (Johnson-Lindenstrauss Flattening Lemma).
• Wednesday, 8/31 : (second) discussion of "what is the concentration of measure phenomenon?" based on isoperimetric inequalities; examples from concentration of measure in Geometry; relation between isoperimetric inequalities and large deviation bounds.
• Monday, 9/5 : Labor Day Holiday - no class. Class made-up on Friday, 9/9.
• Wednesday, 9/7 : Hamming-distance isoperimetric inequality and comparison to Harper's hypercube isoperimetric inequality; Independent Bounded Differences Inequality as a generalization of Chernoff-Hoeffding bounds; proof of the Hamming-distance isoperimetric inequality based on IBDI (an example of the conversion of a large deviation inequlaity to an isoperimetric inequality) ; generalizations of the Hamming-distance isoperimetric inequality leading to Talagrand's convex distance isoperimetric inequality.
• Friday, 9/9 : [make-up class for 9/5] Conversion of the generalized Hamming-distance isoperimetric inequality to a large deviation bound; Conversion of Talagrand inequality to "variable-Hamming distance" large deviation inequality and its application to Stochastic Euclidean Traveling Salesman Problem (using space filling curves).
• Monday, 9/12 : Completion of the application to Euclidean TSP; introduction to the longest increasing subsequence problem.
• Wednesday, 9/14 : Reformulation of Talagrand's inequality for "configuration functions" and its applications to Longest increasing subsequence and Longest common subsequence; Reformulation of Talagrand's inequality for "certifiable functions" (as an extension of configuration functions) with various short applications.
• Monday, 9/19 : No Class due to Trijitzinsky Lectures. Class made-up on Friday, 9/30.
• Wednesday, 9/21 : Proof of the isoperimetric inequality for "certifiable functions" with an application (in random subgraphs) comparing it with IBDI; discussion of geometric interpretation of Talagrand's distance function.
• Monday, 9/26 : Proof of geometric interpretation of Talagrand's distance function; proof of Talagrand's inequality (set-up and base case);
• Wednesday, 9/28 : Completion of the proof of Talagrand's inequality.
• Friday, 9/30 : [make-up class for 9/19] Introduction to Conditional Expectation and Martingales; Basic properties and examples of Martingales; Bounded differences condition and the Azuma-Hoeffding Inequality.
• Monday, 10/3 : Doob's Process (how to create Martingales) with explicit examples; Proof of the Azuma-Hoeffding Inequality.
• Wednesday, 10/5 : Various forms (corollaries) of the Azuma-Hoeffding Inequality; Applications to Chernoff-Hoefding bounds, and chromatic number of random graphs.
• Monday, 10/10 : Comparison of various forms (corollaries) of the Azuma-Hoeffding Inequality applied to the expectation of the chromatic number of random graphs, and occupancy (balls and bins) problem.
• Wednesday, 10/12 : Entropy and Conditional Entropy - definition, motivation, and basic properties; Application of subadditivity to a set system problem.
• Friday, 10/14 : [make-up class for 10/17] Shearer's Lemma - proof and applications to set systems, intersecting set families.
• Monday, 10/17 : No Class due to seminar by Prof. Jozsef Balogh. Class made-up on Friday, 10/14.
• Wednesday, 10/19 : Applications of Shearer's Lemma to intersecting graph families, and to number of copies of a fixed hypergraph in other hypergraphs with given number of edges.
• Friday, 10/21 : [make-up class for 11/14] Review of number of copies of a fixed hypergraph in other hypergraphs with given number of edges; Dedekind's problem and the number of independent sets in a (regular) bipartite graph.
• Monday, 10/24 : Bregman's bound on the number of perfect matchings in a bipartite graph (permanent of a 0-1 matrix); Weighted Shearer's Lemma.
• Wednesday, 10/26 : Weighted Shearer's Lemma with applications to classical inequalities; comments on graph and hypergraph covering problems and Graph Entropy.
• Monday, 10/31 : Markov Chain Monte Carlo (MCMC) Elementary properties of (Homogenous, Discrete time, Finite state) Markov Chains - Ergodicity, Reversibility, Stationary Distribution, Convergence to Stationary Distribution.
• Wednesday, 11/2 : Gibbs Sampler and construction of reversible, ergodic Markov chains with (uniform) stationary distribution for Cartesian product state spaces; examples of uniform sampling for Independent sets and proper q-colorings of graphs; Metropolis process and construction of reversible, ergodic Markov chains with given stationary distribution; Simulated Annealing.
• Friday, 11/4 : [make-up class for 11/16] What is MCMC?; Relationship between (approximate) counting and (almost) uniform sampling; How does sampling help with counting, measuring, etc.; FPRAS, FPAUS and their equivalence for self-reducible problems.
• Monday, 11/7 : Converting a FPAUS into a FPRAS for counting proper q-colorings of a graph; Discussion of Mixing times.
• Wednesday, 11/9 : Coupling and its applications to mixing time - Coupling Lemma; General Coupling Lemma applied to "distance from stationary distribution (as function of time)" to show that it is non-increasing, and exponentially decreasing beyond mixing time.
• Monday, 11/14 : No Class due to conference. Class made-up on Friday, 10/21.
• Wednesday, 11/16 : No Class due to conference. Class made-up on Friday, 11/4.
• Monday, 11/21 : No Class due to Thanksgiving Break.
• Wednesday, 11/23 : No Class due to Thanksgiving Break.
• Monday, 11/28 : Irreducibility of a Markov Chain for proper colorings of a graph; Using coupling to bound the mixing time of a MCMC for proper q-colorings of a graph.
• Wednesday, 11/30 : Path Coupling Lemma and its application to bounding the mixing time of a MCMC.
• Friday, 12/2 : [extra class] Using path coupling to bound the mixing time of a MCMC for the proper q-colorings of a graph; Bounding the mixing time through the spectral gap of the transition matrix.
• Monday, 12/5 : Bounding the mixing time through the spectral gap of the transition matrix; Bounding the spectral gap (and consequently the mixing time) through Conductance, Resistance in network flows, Canonical paths & Congestion in network flows.


• Wednesday, 12/7 : Application of Canonical paths & Congestion to sampling from hypercube; Encoding of canonical paths as a computational simplification for congestion.


• Upcoming Topics : Application of the encoding of Canonical paths & Congestion to sampling from matchings in graph; Application of Resistance to sampling from 0-1 Knapsack solutions (sampling from a truncated hypercube).


• Upcoming Classes :
  
  • Friday, 12/9 : [extra class]