Hardness of sampling solutions from the Symmetric Binary Perceptron

Ahmed El Alaoui, David Gamarnik

We show that two related classes of algorithms, stable algorithms and Boolean circuits with bounded depth, cannot produce an approximate sample from the uniform measure over the se…