In 1984, \textit{L. G. Valiant} [Commun. ACM 27, 1134-1142 (1984; Zbl 0587.68077)] proposed a so-called distribution-free model of learning, in which the learner is given samples of negative and positive examples drawn (according to some unknown probability distributions \(p^ +\), \(p^ -\)) from the sets of all possible positive and negative examples (together, these sets form what is called a representation class). A learning algorithm is called distribution-free if it learns for all possible \(p^ +\) and \(p^ -\). This model is an idealization, because in real life, errors happen: positive examples can be erroneously presented as negative ones, and vice versa. These errors can be not only random, but malicious: e.g., in a military or business confrontation, the opponent wants to prevent us from learning. In view of that, in the paper under review, it is assumed that a certain percentage \(\beta\) of examples that are presented to the learner as ``positive'' or ``negative'' could have been classified erroneously. If \(\beta\) is too big, no learning is possible. As a characteristic that describes the effect of errors on a given representation class \(C\), the authors take the largest \(\beta\) for which learning is still possible. This \(\beta\) is called the optimal malicious learning rate and denoted by \(E_{MAL}\). For several classes \(C\), lower and upper bounds for \(E_{MAL}\) are obtained. For some \(C\), these estimates meet, so for these classes, optimal learning algorithms are presented (optimal in the sense of tolerance to errors). It is also shown that if we use only positive examples, then the values of \(\beta\) for which learning is still possible will become smaller. These problems turn out to be related to combinatorial optimization.