{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreic44avijfvoru5aeoysj4mz6vpohvjbjddlq6zjbzctwrmc5iqdoe",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mflbfahusmz2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.19552v1",
  "publishedAt": "2026-02-24T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Kasper Green Larsen",
    "Markus Engelund Mathiasen",
    "Chirag Pabbaraju",
    "Clement Svendsen"
  ],
  "textContent": "**Authors:** Kasper Green Larsen, Markus Engelund Mathiasen, Chirag Pabbaraju, Clement Svendsen\n\nIn this paper, we consider the problem of replicable realizable PAC learning. We construct a particularly hard learning problem and show a sample complexity lower bound with a close to $(\\log|H|)^{3/2}$ dependence on the size of the hypothesis class $H$. Our proof uses several novel techniques and works by defining a particular Cayley graph associated with $H$ and analyzing a suitable random walk on this graph by examining the spectral properties of its adjacency matrix. Furthermore, we show an almost matching upper bound for the lower bound instance, meaning if a stronger lower bound exists, one would have to consider a different instance of the problem.",
  "title": "The Sample Complexity of Replicable Realizable PAC Learning"
}