I'm trying to understand the proof of theorem 1.6 from the paper "A Matrix Expander Chernoff Bound".

In the proof they say: "Iterating this construction on the remainder a total of $T ≤ k$ times" and later they choose a value for $T$.

$k$ is the length of a given walk on the graph $G$ which has $n$ vertices.

They choose $$T = \frac{2log(\frac{F}{ε})}{1 − λ}$$

If we take $f$ to be a function that gets $1$ on half of the vertices and $-1$ on the other half then $F=\sqrt{n}$ by definition. So $T\gt log(n)$. But $k$ might be much smaller than $log(n)$. So if $T>k$, how can they choose this $T$?


  • $\begingroup$ Looks like you're correct to me, in that this choice is impossible given the constraint of $T \leq k$. However, I haven't really worked through the proof in detail. Why do the authors introduce $T$? Perhaps the authors implicitly intended a different ("trivial") choice of $T$ (perhaps $T=k$) in case the other choice is impossible. But it's equally possible to me that you just found an error. $\endgroup$ – Steve Aug 26 '18 at 20:13

One of the authors of the paper has answered me and he said that they implicitly assume $$k \ge \frac{2 log(\frac{F}{ε})}{1 − λ}$$.

He also said that actually the Theorem would still be true if $k \lt 2 log(F/ε)/(1 − λ)$. In this case, with the same $Z_i$’s, one will actually get $W = 0$ and $|Z_i|_* \le k max_v |f(v)|_*$ trivially.

Additionally, he said that basically Theorem 1.6 is not saying anything for small walks i.e. walks of length less than $2 log(F/ε)/(1 − λ)$. This is a drawback of this Theorem and in the matrix case, one can do much better by other methods as demonstrated by the main result of the paper (Theorem 1.2).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.