Hypercontractive Inequality for Pseudo-Boolean Functions of Bounded Fourier Width

Abstract

A function $f:\{-1,1{\}}^n\to \mathbb{R}$ is called pseudo-Boolean. It is well-known that each pseudo-Boolean function $f$ can be written as $f(x)={\sum }_{I\in \mathcal{F}}\hat{f}(I){\chi }_I(x),$ where $\mathcal{F}\subseteq \{I:I\subseteq [n]\}$, $[n]=\{1,2,...,n\}$, and ${\chi }_I(x)={\prod }_{i\in I}{x}_i$ and $\hat{f}(I)$ are non-zero reals. The degree of $f$ is $\max \{|I|:I\in \mathcal{F}\}$ and the width of $f$ is the minimum integer $\rho$ such that every $i\in [n]$ appears in at most $\rho$ sets in $\mathcal{F}$. For $i\in [n]$, let ${\mathbf{x}}_i$ be a random variable taking values 1 or -1 uniformly and independently from all other variables ${\mathbf{x}}_j$, $j\ne i.$ Let $\mathbf{x}=({\mathbf{x}}_1,...,{\mathbf{x}}_n)$. The $p$-norm of $f$ is $||f|{|}_p=(\mathbb{E}[|f(\mathbf{x}){|}^p]{)}^{1/p}$ for any $p\ge 1$. It is well-known that $||f|{|}_q\ge ||f|{|}_p$ whenever $q>p\ge 1$. However, the higher norm can be bounded by the lower norm times a coefficient not directly depending on $f$: if $f$ is of degree $d$ and $q>p>1$ then $||f|{|}_q\le (\frac{q-1}{p-1}{)}^{d/2}||f|{|}_p.$ This inequality is called the Hypercontractive Inequality. We show that one can replace $d$ by $\rho$ in the Hypercontractive Inequality for each $q>p\ge 2$ as follows: $||f|{|}_q\le ((2r)!{\rho }^{r-1}{)}^{1/(2r)}||f|{|}_p,$ where $r=\lceil q/2\rceil$. For the case $q=4$ and $p=2$, which is important in many applications, we prove a stronger inequality: $||f|{|}_4\le (2\rho +1{)}^{1/4}||f|{|}_2.$

References in corpus (1)

• Systems of Linear Equations over ${\mathbb{F}}_2$ and Problems Parameterized Above Average

Cited by in corpus (1)

• Constraint Satisfaction Problems Parameterized Above or Below Tight Bounds: A Survey