Skip to content
Cairn Commons
X Sign in
Level B · Reproducible Probability P-constant-80a-ising-perceptron-capacity-threshold

Ising perceptron capacity threshold

Let G = (g_ij) be an M × N random matrix with independent standard Gaussian entries, and let Z(G) := | σ ∈ -1,1^N : G σ ≥ 0 coordinatewise |. This is the zero-margin binary (or Ising) perceptron. Write M = ⌊ α N ⌋. Define C_80 to be the infimum of all α > 0 such that ℙ(Z(G) > 0) → 0 as N → ∞.

From the catalogue. Imported from Terence Tao and contributors (optimizationproblems repository) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim.

Start working on it Submit a claim Follow
Cite 
@misc{cairn-constant-80a-ising-perceptron-capacity-threshold,
  title        = {Ising perceptron capacity threshold},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/constant-80a-ising-perceptron-capacity-threshold}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-09-29}
}

Also: CITATION.cff · Atom feed of results

Claims
0
Verified
0
Disputed
0
Refuted
0
On the literature board
0

Current state

No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.

The problem

Description of constant

Let be an random matrix with independent standard Gaussian entries, and let This is the zero-margin binary (or Ising) perceptron. Write .

Define to be the infimum of all such that Equivalently, 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 .

Known upper bounds

BoundReferenceComments
[KR1998]Kim–Roche prove that the capacity is bounded away from with high probability.
[KR1998]Explicit combinatorial upper bound.
[T1999]Independent non-explicit upper bound of the form for some .
[AT2024]Complete proof of the upper bound outlined earlier by Krauth–Mézard.
[H2024]Conditional on an explicit numerical maximization hypothesis for a two-variable function .

Known lower bounds

BoundReferenceComments
Trivial
[KR1998]Shows the capacity is bounded away from zero with high probability.
[DS2025], [NS2023]Conditional on an explicit numerical maximization hypothesis for a one-variable function ; Ding–Sun prove the lower bound with positive probability, and the sharp-threshold theory of Nakajima–Sun upgrades this to with high probability for every .

Additional comments

  • The physics prediction of Krauth–Mézard [KM1989] is that .
  • The literature uses both the names _binary perceptron_ and _Ising perceptron_ for this model.
  • Huang [H2024], together with Ding–Sun [DS2025], gives a conditional proof of the Krauth–Mézard prediction.
  • The explicit upper bound comes from Kim–Roche [KR1998]; Talagrand [T1999] obtained an independent non-explicit upper bound.
  • There are several nearby variants, including the symmetric Ising perceptron, the spherical perceptron, and nonzero-margin perceptrons.

References

  • [KM1989] Krauth, Werner; Mézard, Marc. "Storage capacity of memory networks with binary couplings." _Journal de Physique_ 50, no. 20 (1989): 3057--3066. DOI: 10.1051/jphys:0198900500200305700
  • [KR1998] Kim, Jeong Han; Roche, James R. "Covering Cubes by Random Half Cubes, with Applications to Binary Neural Networks." _Journal of Computer and System Sciences_ 56, no. 2 (1998): 223--252. DOI: 10.1006/jcss.1997.1560
  • [T1999] Talagrand, Michel. "Intersecting random half cubes." _Random Structures & Algorithms_ 15, no. 3-4 (1999): 436--449. DOI: 10.1002/(SICI)1098-2418(199910/12)15:3/4%3C436::AID-RSA11%3E3.0.CO;2-51098-2418(199910/12)15:3/4%3C436::AID-RSA11%3E3.0.CO;2-5)
  • [X2021] Xu, Changji. "Sharp threshold for the Ising perceptron model." _The Annals of Probability_ 49, no. 5 (2021): 2399--2415. DOI: 10.1214/21-AOP1511
  • [NS2023] Nakajima, Shuta; Sun, Nike. "Sharp threshold sequence and universality for Ising perceptron models." In _Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_, 638--674 (2023). DOI: 10.1137/1.9781611977554.ch28
  • [AT2024] Altschuler, Dylan J.; Tikhomirov, Konstantin. "A note on the capacity of the binary perceptron." arXiv (2024), arXiv:2401.15092
  • [H2024] Huang, Brice. "Capacity Threshold for the Ising Perceptron." In _2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)_, 1126--1136 (2024). DOI: 10.1109/FOCS61266.2024.00074; preprint at arXiv:2404.18902
  • [DS2025] Ding, Jian; Sun, Nike. "Capacity lower bound for the Ising perceptron." _Probability Theory and Related Fields_ 193, no. 3-4 (2025): 627--715. DOI: 10.1007/s00440-025-01364-x

What counts as progress

  • A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
  • A formal proof (Lean) of a known bound, or a precise error in a claimed one.
  • New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 2c1968cd520b, Apache License 2.0; reformatted for this page. New records should also be reported there.