Critical percolation distributional complexity exponent conjecture

From papers

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 mm\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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.