Symmetric Perceptrons, Number Partitioning and Lattices

Neekon Vafa, Vinod Vaikuntanathan

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