Critical percolation distributional complexity exponent conjecture

About 2 years old · traced to

Let GmG_m be the square-lattice percolation graph in an mm-by-mm square, let fmf_m be the Boolean function indicating an open left-to-right crossing, and let π1/2\pi_{1/2} denote critical percolation. The quantities s(fm,π1/2)s(f_m,\pi_{1/2}), w(fm,π1/2)w(f_m,\pi_{1/2}), ℓ(fm,π1/2)\ell(f_m,\pi_{1/2}), and a(fm,π1/2)a(f_m,\pi_{1/2}) are the distributional sensitivity, witness, randomized decision-tree, and algorithmic complexities, respectively.

Critical percolation complexity conjecture. As m→∞m\to\infty,

s(fm,π1/2)=m3/4+o(1),s(f_m,\pi_{1/2})=m^{3/4+o(1)}, w(fm,π1/2)≤m4/3+o(1),w(f_m,\pi_{1/2})\le m^{4/3+o(1)}, ℓ(fm,π1/2)≥m3/2+o(1),\ell(f_m,\pi_{1/2})\ge m^{3/2+o(1)},

and

a(fm,π1/2)≤m7/4+o(1).a(f_m,\pi_{1/2})\le m^{7/4+o(1)}.

These predictions arise from the conjectured four-, three-, and two-arm exponents 5/45/4, 2/32/3, and 1/41/4, respectively; determining the exact exponents in the relevant cases is a well-known open problem, while the corresponding conformal-invariance results are known for critical site percolation on the triangular lattice.

References

Primary source

Laurin Köhler-Schindler and Jeffrey E. Steif, “A study of distributional complexity measures for Boolean functions”, arXiv:2408.12995 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.