3 problems

Let $p$ be odd and fix an integer $\ell\in[\lfloor p/2\rfloor,n-\lceil p/2\rceil]$. For $S\subseteq[n]$ with $|S|=\ell$ and $T\subseteq[n]$ with $|T|=\ell+1$, define the rectangula…

For an average-case problem, consider algorithms based on the Kikuchi free energy and algorithms based on the sum-of-squares hierarchy. Kikuchi free-energy optimality conjecture. F…

Fix an integer $p$ and let $\ell$ be constant independently of $n$. Log-free performance conjecture. There exists a constant $c_p(\ell)>0$, with $c_p(\ell)\to 0$ as $\ell\to\infty$…