The notable KKL Theorem of Kahn, Kalai, and Linial says that if f : {0,1}^n -> {0,1} is a balanced boolean function, then there is at least one coordinate i with "influence" at least Omega(log n / n). We generalize this result to boolean functions on Cayley and Schreier graphs, whenever the generating set is a union of conjugacy classes and the associated Markov chain has a good log-Sobolev constant. E.g., we show that if f is a balanced boolean function on the set of n-bit strings with Hamming weight n/2, then there exists some pair of indices i, j such that the influence on f of swapping the ith and jth coordinates is at least Omega(log n / n). As an application we prove a new "robustification" of the classical Kruskal-Katona Theorem from combinatorics. We also discuss an application in computational learning theory. This talk is based on two joint works with Karl Wimmer of Duquesne University.