Supplementary Appendix for: Algorithms and Hardness for Learning Linear Thresholds from Label Proportions

Further, we have the following. Therefore, let us consider 0 p 1 / 2 . Differentiating w.r.t we obtain, @ ( p,) @ = (6 p 4) + 2(1 p), and, @ Observing that (1 / 3, 2 / 3) = 4 / 9 completes the analysis. Our hardness result is via a reduction from the Smooth-Label-Cover problem defined below. Theorem 4.1 directly follows from the following theorem.