FR3.R4.1

On the Optimality of Dictator functions and Isoperimetric Inequalities on Boolean Hypercubes

Zijie Chen, Chandra NAIR, The Chinese University of Hong Kong, Hong Kong SAR of China

Session:
Information Inequalities 2

Track:
9: Shannon Theory

Location:
Omikron II

Presentation Time:
Fri, 12 Jul, 14:35 - 14:55

Session Chair:
Venkat Anantharam, University of California, Berkeley
Abstract
In this paper, we present a family of conjectures on the optimality of the dictator function among all Boolean functions for a new family of $\Phi$-entropies. Our main theorem shows that there is an ordering of these conjectures, in that if the conjecture is established for a value $\alpha$, then it holds for any $\beta: \beta \geq \alpha$. For the parameter range $\frac 12 \leq \alpha,\beta < 1$, this family of conjectures is stronger than the mutual information conjecture, originally proposed in a paper by Courtade and Kumar. By considering a limiting value of the noise parameter $\rho$, we show how these conjectures relate to isoperimetric inequalities on the Boolean Hypercube of a flavor first considered by Talagrand and later by Kahn and Park. Finally, we obtain bounds to our conjecture using ideas from the proofs of isoperimetric inequalities.
Resources