$\begin{align*} &\text{min } \epsilon \\ &|f(x) - \sum_{|S|\leq d} c_S \chi_S(x)| \leq \epsilon, \ \ \ x \in D \\ &|\sum_{|S| \leq d} c_S \chi_S(x)| \leq 1 + \epsilon, \ \ \ x \in \{-1,1\}^n \setminus D\\ &\epsilon \geq 0 \end{align*}$
Consider this primal LP where $p(x) = \sum_{|S|\leq d} c_S \chi_S(x)$ is a multilinear polynomial of degree $\leq d$, and minimization is over $\epsilon \ and \ c_S$.
It is given that the dual LP for this is given by
$\begin{align*} &\text{max } \sum_{x \in D} f(x)\phi(x) - \sum_{x \in \{-1,1\}^n\setminus D} |\phi(x)|\\ &\sum_{x \in \{-1,1\}^n} |\phi(x)| = 1\\ & \sum_{x \in \{-1,1\}^n} \phi(x)\chi_S(x) = 0, \ \ \ for \ all \ |S| \leq d \\ & \phi(x) \in \mathbb{R}\\ \end{align*}$
Can someone explain how is this the dual of the primal LP?
