Algorithms and barriers in the symmetric binary perceptron model

DOI10.1109/FOCS54457.2022.00061MaRDI QIDQ6943031zbMATH OpenFDO

Authors David Gamarnik, C. J. Xu, Eren C. Kızıldağ, Will Perkins

Publication date 15 August 2025

Full work available at URL https://doi.org/10.1109/FOCS54457.2022.00061

Mathematics Subject Classification ID

Proceedings, conferences, collections, etc. pertaining to computer science (68-06)

Cited in

(12)

• Quantum glassiness from efficient learning
• Capacity lower bound for the Ising perceptron
• Average-case matrix discrepancy: satisfiability bounds
• Shattering in the Ising p-spin glass model
• Zero-one laws for random feasibility problems
• Weaver's discrepancy for Gaussian random vectors
• How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states
• The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties
• A CLuP algorithm to practically achieve 0.76 SK-model ground state free energy
• Overlap gap and computational thresholds in the square wave perceptron
• Sharp phase transitions for the overlap gap property
• Sharp thresholds for the overlap gap property: Ising p-spin Glass and random k-SAT

This page was built for publication: Algorithms and barriers in the symmetric binary perceptron model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6943031)