Submit progress

on Ising perceptron capacity threshold ($C_{80}$)

The statement

Let $G = (g_{ij})$ be an $M \times N$ random matrix with independent standard Gaussian entries, and let

Z(G) := \left| \left\{ \sigma \in \{-1,1\}^N : G \sigma \geq 0 \text{ coordinatewise} \right\} \right|.

This is the zero-margin binary (or Ising) perceptron. Write $M = \lfloor \alpha N \rfloor$ .

Define $C_{80}$ to be the infimum of all $\alpha > 0$ such that

\mathbb{P}(Z(G) > 0) \to 0 \qquad \text{as } N \to \infty.

Equivalently, $C_{80}$ is the asymptotic storage-capacity / satisfiability threshold of the zero-margin Ising perceptron. Sharp-threshold results [X2021], [NS2023] show that this formulation captures the threshold location up to $o(1)$ .

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.