| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

1. Entropic methods

    1. Entropy Freiman-Ruzsa lower bounds

          Theorem. Let $X$ be any $\mathbb{F}_2^n$-valued random variable such that $d[X,X]\leq \log K$, where $d$ is the entropic Ruzsa distance. Then there is a subspace $H\subset \mathbb{F}_2^n$ such that $d[X,U_H]\leq 11\log K$, where $U_H$ is uniform on $H$.

      Add remark

      Problem 1.1.

      [Terence Tao] Can we give lower bounds for $d[X,U_H]$?

        • Entropy proof of Sidorenko

              There is a proof system for graph homomorphism inequalities using flag algebras.

          Add remark

          Problem 1.2.

          [Yufei Zhao] Define a proof system for graph homomorphism inequalities using entropy.
              For example, prove that "$H$ is Sidorenko" is not provable in this proof system, for $H=K_{5,5}\setminus C_{10}$.

          Can all known cases of Sidorenko be entropized?

          Can the proof that even girth graphs are locally Sidorenko be entropized?

            • Inverse theorems with polynomial bounds

                  Given $f:\mathbb{F}_2^n\to \mathbb{F}_2^m$ with $\mathbb{P}_{x+y=z+w}(f(x)+f(y)=f(z)+f(w))\geq \epsilon$, then Polynomial Freiman-Ruzsa implies that $f$ correlates with a linear function.

              Set $D_hf(x)=f(x+h)-f(x)$. If $\mathbb{P}_{x,h_1,h_2,h_3}(D_{h_1}D_{h_2}D_{h_3}f(x)=0)\geq \epsilon$, then PFR implies that $f$ correlates with a quadratic function.

              Add remark

              Problem 1.3.

              [Freddie Manners] Is there a direct entropic proof of the above results with polynomial bounds?
                  The second result is known with bounds $1/\exp(\exp(1/\epsilon))$.

                  Cite this as: AimPL: High-dimensional phenomena in discrete analysis, available at http://aimpl.org/highdimdiscrete.