Reviews: Graph-based Discriminators: Sample Complexity and Expressiveness

Originality: The paper introduces a new notion of VC-dimension for k-ary Boolean functions that controls the sample complexity of graph-based discriminators. I do not think that such a notion of VC-dimension has been considered in the literature. Quality: The main results and the proofs generally seem to be correct. All the main claims in the paper are supported with complete proofs or references to proofs in the literature. I did not check all the proofs in detail; I read the proofs of Theorem 2 and Lemma 1 and they seem to be correct (but please check for typos; some of them are mentioned below under "Minor Comments").