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.