Symmetric Perceptrons, Number Partitioning and Lattices

Neekon Vafa, Vinod Vaikuntanathan

The symmetric binary perceptron (${\mathrm{SBP}}_{\kappa }$) problem with parameter $\kappa :{\mathbb{R}}_{\ge 1}\to [0,1]$ is an average-case search problem defined as follows: given a random Gau…