Loading Web-Font TeX/Math/Italic
| 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.