Online Algorithms Cannot Find Isolated Perceptron Solutions
cs.CC, cs.DS, math-ph, math.MP, math.PR
Submitted: 2026-11-02
Updated: 2026-11-02
Terminology
Sources
- Optimal Online Discrepancy Minimization in Linear Time
- A note on the capacity of the binary perceptron
- When low-loss paths make a binary neuron trainable: detecting algorithmic transitions with the connected ensemble
- Overlap Gap and Computational Thresholds in the Square Wave Perceptron
- Collision Resistance of Single-Layer Neural Nets
- Detailed proof of Nazarov's inequality
- Sharp Online Hardness for Large Balanced Independent Sets
- The Mean-Field Limit of Online Stochastic Vector Balancing
- Optimal Hardness of Online Algorithms for Large Independent Sets
- Strong freezing in binary perceptron models
- Uniqueness of Replica-symmetric Saddle Point for Ising Perceptron
- The storage capacity of the Ising perceptron: verification of the outstanding numerical conditions
- Another look at the Gardner problem
- Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?