It is mentioned in Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates, A. Gal et al. that "it is also not hard to show that (pairwise-independent) hashing circuits satisfy the superconcentrator property 1", which is

For each $k\in\{1,2,\dots,m\}$, for each $X$ and $Y$ of size $k$, $f(X,Y)\geq\delta k$, where $X$ is a subset of input vertices and $Y$ is a subset of output vertices, $f(X,Y)$ is the maximum number of vertex-disjoint paths from $X$ to $Y$ and $\delta$ is a constant such that $0<\delta\leq1$.

However I have found nowhere the proof to this statement, and I cannot come up with one myself. The method used in Gal's paper proving all linear code circuits are weaker superconcentrators does not apply well because it uses the weaker definition involving probabilistic argument that $Y$ is chosen randomly instead of arbitrarily.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.