Overlap Gap and Computational Thresholds in the Square Wave Perceptron

2025/06/05 by Marco Benedetti, Benedetti, Marco, Andrej Bogdanov +13 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Disordered Systems and Neural Networks (cond-mat.dis-nn) #FOS: Physical sciences #Neural Networks and Applications #Quantum Computing Algorithms and Architecture

paper · pdf · doi:10.48550/arxiv.2506.05197

openalex publication_date 2025/06/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Square Wave Perceptrons (SWPs) form a class of neural network models with oscillating activation function that exhibit intriguing ``hardness'' properties in the high-dimensional limit at a fixed constraint density α= O(1). In this work, we examine two key aspects of these models. The first is related to the so-called overlap-gap property, that is a disconnectivity feature of the geometry of the solution space of combinatorial optimization problems proven to cause the failure of a large family of solvers, and conjectured to be a symptom of algorithmic hardness. We identify, both in the storage and in the teacher-student settings, the emergence of an overlap gap at a threshold α_OGP(δ), which can be made arbitrarily small by suitably increasing the frequency of oscillations 1/δ of the activation. This suggests that in this small-δ regime, typical instances of the problem are hard to solve even for small values of α. Second, in the teacher-student setup, we show that the recovery threshold of the planted signal for message-passing algorithms can be made arbitrarily large by reducing δ. These properties make SWPs both a challenging benchmark for algorithms and an interesting candidate for cryptographic applications.

Citations

• Are Neural Networks Collision Resistant?
• Symmetric Perceptrons, Number Partitioning and Lattices
• Some easy optimization problems have the overlap-gap property
• Fundamental computational limits of weak learnability in high-dimensional multi-index models
• Capacity threshold for the Ising perceptron
• Computational-Statistical Gaps in Gaussian Single-Index Models
• Typical and atypical solutions in non-convex neural networks with discrete and continuous weights
• Algorithms and Barriers in the Symmetric Binary Perceptron Model
• Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster
• On the Cryptographic Hardness of Learning Single Periodic Neurons
• Frozen 1-RSB structure of the symmetric Ising perceptron
• Optimal Low-Degree Hardness of Maximum Independent Set
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics
• The Overlap Gap Property and Approximate Message Passing Algorithms for\n p-spin models
• The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
• On-Line Balancing of Random Inputs
• Capacity lower bound for the Ising perceptron
• Fundamental Limits of Weak Recovery with Applications to Phase Retrieval
• Statistical physics of inference: thresholds and algorithms
• On the Complexity of Random Satisfiability Problems with Planted Solutions
• On the Solution-Space Geometry of Random Constraint Satisfaction Problems
• Clustering of solutions in the random satisfiability problem
• Three unfinished works on the optimal storage capacity of networks
• The space of interactions in neural network models
• The perceptron: A probabilistic model for information storage and organization in the brain.

Cited by

• Are Neural Networks Collision Resistant?

Related

• Algorithms and Barriers in the Symmetric Binary Perceptron Model
• Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization
• Are Neural Networks Collision Resistant?
• On the robustness of noisy solutions in non-convex neural networks
• Binary perceptron computational gap -- a parametric fl RDT view