  Perceptrons have been known for a long time as a promising tool within the
neural networks theory. The analytical treatment for a special class of
perceptrons started in seminal work of Gardner \cite{Gar88}. Techniques
initially employed to characterize perceptrons relied on a statistical
mechanics approach. Many of such predictions obtained in \cite{Gar88} (and in a
follow-up \cite{GarDer88}) were later on established rigorously as mathematical
facts (see, e.g.
\cite{SchTir02,SchTir03,TalBook,StojnicGardGen13,StojnicGardSphNeg13,StojnicGardSphErr13}).
These typically related to spherical perceptrons. A lot of work has been done
related to various other types of perceptrons. Among the most challenging ones
are what we will refer to as the discrete perceptrons. An introductory
statistical mechanics treatment of such perceptrons was given in
\cite{GutSte90}. Relying on results of \cite{Gar88}, \cite{GutSte90}
characterized many of the features of several types of discrete perceptrons. We
in this paper, consider a similar subclass of discrete perceptrons and provide
a mathematically rigorous set of results related to their performance. As it
will turn out, many of the statistical mechanics predictions obtained for
discrete predictions will in fact appear as mathematically provable bounds.
This will in a way emulate a similar type of behavior we observed in
\cite{StojnicGardGen13,StojnicGardSphNeg13,StojnicGardSphErr13} when studying
spherical perceptrons.
