{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreig4m6mafjnsevfujz3dtbr6g53q4tnhmhurttnbmptjyrp6eeacm4",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mlkmawfrpan2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.08072v1",
  "publishedAt": "2026-05-11T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Jane H. Lee",
    "Anay Mehrotra",
    "Manolis Zampetakis"
  ],
  "textContent": "**Authors:** Jane H. Lee, Anay Mehrotra, Manolis Zampetakis\n\n$L_1$-Approximating polynomials, i.e., polynomials that approximate indicator functions in $L_1$-norm under certain distributions, are widely used in computational learning theory. We study the existence of \\textit{non-negative} $L_1$-approximating polynomials with respect to Gaussian distributions. This is a stronger requirement than $L_1$-approximation but weaker than sandwiching polynomials (which themselves have many applications). These non-negative approximating polynomials have recently found uses in smoothed learning from positive-only examples. In this short note, we prove that every class of sets with Gaussian surface area (GSA) at most $Γ$ under the standard Gaussian admits degree-$k$ non-negative polynomials that $\\eps$-approximate its indicator functions in $L_1$-norm, for $k=\\tilde{O}(Γ^2/\\varepsilon^2)$. Equivalently, finite GSA implies $L_1$-approximation with the stronger pointwise guarantee that the approximating polynomial has range contained in $[0,\\infty)$. Up to a constant-factor, this matches the degree of the best currently known Gaussian $L_1$-approximation degree bound without the non-negativity constraint.",
  "title": "A Note on Non-Negative $L_1$-Approximating Polynomials"
}