Background ======== The paper considers the important challenge of generalization theory for dependent variables. Dependency graphs provide a natural and convenient method for capturing such dependencies where two subsets of RV are independent iff they are non-adjacent. Several previous results included generalization of Hoeffding's inequality that is useful in the context of bounding the deviation of the average of (dependent) RV from their mean. Main result ======= McDiarmid-type are more general and allow analyzing the deviation of any Lipschitz function from its mean. The main contribution paper is a McDiarmid inequality for graph dependent RV in terms of the Lipschitz constants corresponding to the dependent RV. Application ======== Stability bounds provide a great motivation for McDiarmid-type inequalities. The authors suggest high probability stability bounds for dependent variables and illustrate the applicability for learning in m-dependent data. Overall I find the contribution significant and interesting.

I read about 75% of the paper and what I read seems to be correct.

This is a solid paper which addresses an important problem in a novel way. It is very well written, as the Authors guide the reader through the presentation of novel concepts, and they do a good job at easing the reader into the subject with a good review of existing works. The results are very interesting and they should have significant impact. While I haven't checked all the proofs, the reasoning seems correct, and the results are in line with the intuition.