{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreif5tedlmnihdwq775aah4rv6stlmtvbd3mbt6dzhhrqvbpkdo2sai",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mkkzpvcecdy2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.23958v1",
  "publishedAt": "2026-04-28T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Marco Carmosino",
    "Ngu Dang",
    "Tim Jackman"
  ],
  "textContent": "**Authors:** Marco Carmosino, Ngu Dang, Tim Jackman\n\nGate elimination is the primary technique for proving explicit lower bounds against general Boolean circuits, including Li and Yang's state-of-the-art $3.1n - o(n)$ bound for affine dispersers (STOC 2022). Every circuit lower bound is implicitly existential: every circuit that is too small to compute $f$ must err on some input. This raises a natural question: are these lower bounds \\emph{constructive}? That is, can we efficiently produce such errors? Chen, Jin, Santhanam, and Williams showed that constructivity plays a central role in many longstanding open problems in complexity theory, and explicitly raised the question of which circuit lower bound techniques can be made constructive (FOCS 2021). We show that a variety of gate elimination arguments yield refuters -- efficient algorithms that, when given a circuit that is too small to compute a function $f$, produce an input on which the circuit errs. Our results range from elementary lower bounds for $XOR$ and the multiplexer to more sophisticated arguments for affine dispersers. Underlying these results is a shift in perspective: gate elimination arguments \\emph{are} algorithms. Each step either simplifies the circuit or reveals a violation of some structural or functional property, from which, with a little additional work, explicit counterexamples can be extracted. We further strengthen the $XOR$ result to handle circuits that \\emph{match} the lower bound: given any DeMorgan circuit of size $3(n-1)$ that fails to compute $XOR_n$, we can efficiently produce a counterexample. While refuters follow from the gate elimination arguments themselves, this refinement requires a complete characterization of the set of optimal circuits computing $XOR$ -- a requirement rarely met by other explicit functions.",
  "title": "Constructive Separations from Gate Elimination"
}