Hardness of sampling solutions from the symmetric binary perceptron

DOI10.1002/RSA.70021MaRDI QIDQ6938018zbMATH OpenFDO

Authors Ahmed El Alaoui, David Gamarnik

Publication date 26 August 2025

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/RSA.70021

zbMATH Keywords

Boolean circuitsdisorder chaosperceptronsamplingstable algorithms

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20)

Cited in

(2)

• Near-optimal shattering in the Ising pure p-spin and rarity of solutions returned by stable algorithms
• Generative diffusion for perceptron problems: statistical physics analysis and efficient algorithms

This page was built for publication: Hardness of sampling solutions from the symmetric binary perceptron

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