Graphs of Joint Types, Noninteractive Simulation, and Stronger Hypercontractivity

Authors Lei Yu, Venkat Anantharam, Jun Chen

Abstract: In this paper, we study the emph{type graph}, namely a bipartite graph induced by a joint type. We investigate the maximum edge density of induced bipartite subgraphs of this graph having a number of vertices on each side on an exponential scale in the length

n

of the type. This can be seen as an isoperimetric problem. We provide asymptotically sharp bounds for the exponent of the maximum edge density as the length of the type goes to infinity. We also study the biclique rate region of the type graph, which is defined as the set of

l e f t (R_{1}, R_{2} i g h t)

such that there exists a biclique of the type graph which has respectively

e^{n R_{1}}

and

e^{n R_{2}}

vertices on the two sides. We provide asymptotically sharp bounds for the biclique rate region as well. We then apply our results and proof ideas to noninteractive simulation problems. We completely characterize the exponents of maximum and minimum joint probabilities when the marginal probabilities vanish exponentially fast with given exponents. These results can be seen as strong small-set expansion theorems. We extend the noninteractive simulation problem by replacing Boolean functions with arbitrary nonnegative functions, and obtain new hypercontractivity inequalities which are stronger than the common hypercontractivity inequalities. Furthermore, as an application of our results, a new outer bound for the zero-error capacity region of the binary adder channel is provided, which improves the previously best known bound, due to Austrin, Kaski, Koivisto, and Nederlof. Our proofs in this paper are based on the method of types, linear algebra, and coupling techniques.

This page was built for publication: Graphs of Joint Types, Noninteractive Simulation, and Stronger Hypercontractivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6505055)