Two-sided 60/40 majority: prediction, counting, and compatibility

We give self-contained prediction guarantees for two precise interpretations of the two-sided majority with a 60/40 gap from Blum and Balcan, Open Problems in Efficient Semi-Supervised PAC Learning (COLT 2007). When the percentages are taken within the positive and negative indicator groups, centering the Boolean coordinates gives a Euclidean margin of 1/5. A perceptron with an elementary stopping rule learns from at most 26⌈ε-1 ln(26/δ)⌉ labeled examples, independently of dimension. When the percentages are taken among the active indicators, we prove the distribution-free counting inequality ln Kε ≥ εn/5 − ln 2, where Kε is the number of hypotheses whose incompatibility is at most ε. A normalized perceptron consequently uses O(B2 log(2+B)) labels, where B = (ln Kε + ln(1/δ))/ε is the raw-count benchmark. Both procedures have polynomial bit complexity and require no additional unlabeled observations. The first appendix gives a polynomial-time learner returning a signed-literal majority, with a sample bound proved by compressed descriptions. The second proves NP-completeness of finding an exactly compatible partition and derives an NP = RP consequence for general polynomial-time learning with an output-compatibility guarantee. The classical learning mechanisms are identified explicitly, and the results are compared with the polynomial prediction criterion in the Blum–Balcan question under stated normalization and output conventions. Files: the manuscript (PDF) and the complete package (LaTeX source, Python code, verification scripts and results, internal audit reports). Contact: [email protected]