From Expanders to Hitting Distributions and Simulation Theorems

Abstract

In this paper we explore hitting distributions, a notion that arose recently in the context of deterministic "query-to-communication" simulation theorems. We show that any expander in which any two distinct vertices have at most one common neighbor can be transformed into a gadget possessing good hitting distributions. We demonstrate that this result is applicable to affine plane expanders and to Lubotzky-Phillips-Sarnak construction of Ramanujan graphs . In particular, from affine plane expanders we extract a gadget achieving the best known trade-off between the arity of outer function and the size of gadget. More specifically, when this gadget has k bits on input, it admits a simulation theorem for all outer function of arity roughly 2^(k/2) or less (the same was also known for k-bit Inner Product). In addition we show that, unlike Inner Product, underlying hitting distributions in our new gadget are "polynomial-time listable" in the sense that their supports can be written down in time 2^O(k), i.e. in time polynomial in size of gadget's matrix.
We also obtain two results showing that with current technique no better trade-off between the arity of outer function and the size of gadget can be achieved. Namely, we observe that no gadget can have hitting distributions with significantly better parameters than Inner Product or our new affine plane gadget. We also show that Thickness Lemma, a place which causes restrictions on the arity of outer functions in proofs of simulation theorems, is unimprovable.