{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreidxp5m673bmkfiyrn4i27u52ekyfjw73zezu3cravsn4zerhppxiy",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mgqrxvyread2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.08033v1",
  "publishedAt": "2026-03-10T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Kirill Krinkin"
  ],
  "textContent": "**Authors:** Kirill Krinkin\n\nWe study the gap between the minimum size of a Boolean circuit (DAG) and the minimum size of a formula (tree circuit) over the And-Inverter Graph (AIG) basis {AND, NOT} with free inversions. We prove that this gap is always 0 or 1 (Unit Gap Theorem), that sharing requires opt(f) >= n essential variables (Threshold Theorem), and that no sharing is needed when opt(f) <= 3 (Tree Theorem). Gate counts in optimal circuits satisfy an exact decomposition formula with a binary sharing term. When the gap equals 1, it arises from exactly one gate with fan-out 2, employing either dual-polarity or same-polarity reuse; we prove that no other sharing structure can produce a unit gap.",
  "title": "The Unit Gap: How Sharing Works in Boolean Circuits"
}