The Unit Gap: How Sharing Works in Boolean Circuits

This paper establishes that the size difference between optimal Boolean circuits and formulas over the AIG basis is strictly limited to 0 or 1, characterizing the precise conditions under which sharing occurs and proving that any non-zero gap arises exclusively from a single gate with fan-out 2.

The Gist

Imagine you are a master architect tasked with building a machine to solve a specific logic puzzle. You have two blueprints to choose from:

1. The "Tree" Blueprint (Formula): This is a strict, one-way street. Every time you build a component (a logic gate), you can only use it once. If you need that same component again later, you have to build a brand new, identical copy from scratch. It's like baking a cake where every time you need an egg, you have to crack a new one, even if you just cracked one a second ago.
2. The "Forest" Blueprint (Circuit): This is a flexible network. You can build a component once and then pipe its output to multiple places. It's like cracking one egg and using it in both the batter and the frosting. This "sharing" usually saves you a lot of work (gates).

For decades, computer scientists wondered: How much work can you actually save by sharing? In some complex worlds, sharing can save you a massive amount of work—turning a mountain of bricks into a pebble.

But this paper, by Kirill Krinkin, looks at a very specific, modern type of machine (called an AIG or And-Inverter Graph) used in real-world chip design. The author asks: In this specific world, how much can sharing actually help?

The Big Discovery: The "Unit Gap"

The author proves a surprising and simple rule: In this specific world, sharing can save you either 0 bricks or exactly 1 brick. Never more.

Think of it like this:

• If you build a "Tree" machine, it might take 100 steps.
• If you build a "Forest" machine (sharing parts), it might take 99 steps.
• It will never take 50 steps. The savings are capped at a single unit.

This is called the Unit Gap Theorem. It means that for these specific machines, the "Tree" blueprint is almost always perfect. You only need to switch to the "Forest" blueprint if you can save exactly one tiny step.

When Does Sharing Even Happen?

The paper also finds a "Threshold" for when sharing is even possible.

• The Rule: You can't share anything unless your machine is complex enough to have at least as many "essential ingredients" (variables) as the number of steps it takes to build.
• The Analogy: Imagine trying to share a tool in a workshop. If you only have 2 tools and 2 workers, you don't need to share; everyone has their own. But if you have 5 workers and only 4 tools, someone has to share.
• The Finding: If your machine is very small (3 steps or fewer), sharing is impossible. You must use the Tree blueprint. Sharing only kicks in once the machine gets big enough (at least 4 steps).

How Does the Saving Happen? (The Two Tricks)

If you do manage to save that one precious brick, how do you do it? The author found there are only two magic tricks used in the entire universe of these machines:

1. The "Double-Flip" Trick (Dual-Polarity):
   Imagine you build a component, but you need to use it once as "ON" and once as "OFF." In a Tree blueprint, you'd have to build two separate components. In the Forest, you build one, and you just flip the switch on one of the wires leading out of it. It's like having a light switch that controls two lights: one bright, one dim, using the same bulb.

   • Result: You save 1 brick.

2. The "Copy-Paste" Trick (Common Subexpression):
   Imagine you build a complex sub-machine, and two different parts of your main machine need to use it exactly the same way. In a Tree, you build it twice. In a Forest, you build it once and send the signal to both places.

   • Result: You save 1 brick.

The paper proves that no other tricks exist. You can't save 2 bricks, and you can't use a third, weirder method to save 1 brick. It's strictly these two moves.

Why Should You Care?

This might sound like a tiny detail (saving just 1 brick), but it's actually huge for how computers are designed today.

1. Predictability: Chip designers use software to optimize circuits. Knowing that the "Tree" version is almost always the best, and that the "Forest" version can only ever be one step better, makes the optimization problem much simpler. The software doesn't need to look for massive shortcuts; it just needs to check for these two specific "one-step" tricks.
2. Structure over Size: The paper shows that the structure of these machines is very rigid. They are "atomic." You can't have a complex web of sharing; it's usually just one single point where two paths merge.
3. The "Free Constant" Secret: The reason this works is that in this specific system, the number "1" is free (it costs nothing to have a constant "true" signal). This allows for a mathematical trick that collapses the gap. If you change the rules (remove the free "1"), the gap could explode again.

The Bottom Line

Think of this paper as a map for a very specific, tiny island.

• Old Map: "The island is huge, and you might find a shortcut that cuts your journey in half!"
• New Map: "Actually, the island is small. The only shortcut you can find is a single step to the left. And there are only two specific places on the island where you can take that step."

It turns a chaotic, complex problem into a clean, predictable rule: In modern chip design, sharing is rare, it's limited to saving exactly one step, and it happens in only two very specific ways.

Technical Summary

Here is a detailed technical summary of the paper "The Unit Gap: How Sharing Works in Boolean Circuits" by Kirill Krinkin.

1. Problem Statement

The paper investigates the fundamental difference in size between Boolean circuits (Directed Acyclic Graphs, or DAGs) and Boolean formulas (Tree circuits) over the And-Inverter Graph (AIG) basis $\{AND, NOT\}$ with free inversions.

• Context: In general circuit complexity, formulas can be exponentially larger than circuits because formulas cannot reuse intermediate results (fan-out must be 1), whereas circuits can share sub-expressions (fan-out $>1$).
• Specific Gap: The author focuses on the "gap" defined as $gap(f) = tree(f) - opt(f)$, where $tree(f)$ is the minimum formula size and $opt(f)$ is the minimum circuit size.
• The AIG Basis: The study is restricted to AIGs, a canonical representation in modern logic synthesis tools (like ABC). Key features of this basis are:
  • Size is measured by the number of 2-input AND gates.
  • Inversion (NOT) is "free" (an edge attribute, not a gate).
  • The constant $1$ is available at zero cost.

The central question is: How much does sharing (reusing a gate) reduce the size of an optimal AIG circuit compared to a formula, and what is the structural nature of this reduction?

2. Methodology

The author employs a hybrid approach combining rigorous theoretical proofs with exhaustive computational enumeration and SAT-based synthesis.

• Theoretical Framework:
  • Uses NPN equivalence (Negation, Permutation, Negation of output) to classify functions.
  • Applies Gate Elimination arguments (Lemma 1) to establish lower bounds based on the number of essential variables.
  • Utilizes Decomposition Analysis to break down functions into sub-functions ($f = a \land b$).
  • Introduces a Tropical Algebra interpretation (min-plus semiring) to model the recursion of tree sizes versus circuit sizes.
• Computational Experiments:
  • Complete Enumeration: All $2^{2^n}$functions for$n=3$(256 functions) and$n=4$ (65,536 functions).
  • SAT-Based Synthesis: Used for $n=5$ and $n=6$ to find optimal circuits for specific subsets of functions (e.g., those with specific optimal sizes).
  • Generative Grammar: A structural probe used to generate random AIGs and test optimality rates and mutational robustness.
• Verification: The results are verified against known bounds and exhaustive data sets up to $n=4$.

3. Key Contributions and Theorems

The paper establishes five main structural theorems characterizing the relationship between formulas and circuits in the AIG basis:

A. The Unit Gap Theorem (Theorem 2)

• Statement: For every Boolean function $f$ in the AIG basis with free inversions, the gap is strictly 0 or 1.
  $$gap(f) \in \{0, 1\}$$
• Significance: This is a stark contrast to general bases where the gap can be superpolynomial. The bound of 1 arises because:
  1. The constant $1$is free, allowing the trivial decomposition$f = 1 \land f$ (which adds exactly 1 gate to the formula size).
  2. Free inversions mean $opt(f) = opt(\bar{f})$.
• Implication: Sharing in optimal AIGs is "atomic." An optimal circuit deviates from a tree structure by at most a single reconvergent point.

B. The Threshold Theorem (Theorem 3)

• Statement: If a function $f$ has $n$ essential variables and $gap(f) = 1$, then the optimal circuit size must satisfy:
  $$opt(f) \ge n$$
• Significance: Sharing (and thus a gap of 1) cannot occur in small circuits. A function must have a complexity of at least equal to its number of variables to benefit from sharing.

C. The Tree Theorem (Theorem 4)

• Statement: If $opt(f) \le 3$, then $gap(f) = 0$.
• Significance: No sharing is possible for circuits of size 3 or less. The first opportunity for a gap of 1 appears at $opt(f) = 4$ (for $n=3,4$) or $opt(f)=5$ (for $n=5$).

D. The Decomposition Formula (Corollary 6)

• Statement: For any gate $g$ in an optimal circuit computing $f = a \land b$, the size satisfies:
  $$opt(f) = 1 + opt(a) + opt(b) - s(a, b)$$
  where $s(a, b) \in \{0, 1\}$ is a binary term counting shared gates between the sub-DAGs of $a$ and $b$.
• Significance: This provides an exact recursive formula for circuit complexity. Unlike standard Bellman equations, the sharing term $s(a,b)$ depends on the global optimal solution, not just local subproblems.

E. The Two-Mechanism Theorem (Theorem 7)

• Statement: When $gap(f) = 1$, the sharing arises from exactly one gate with fan-out 2. This sharing occurs via one of two specific mechanisms:
  1. Dual-Polarity Reuse: The shared gate is used in both positive and negative polarities (e.g., feeding an XOR structure).
  2. Same-Polarity Reuse (Common Subexpression - CSE): The shared gate is used twice in the same polarity by disjoint branches.
• Significance: These are the only two structural mechanisms that produce a unit gap in the AIG basis. No other complex sharing structures exist for optimal AIGs.

4. Detailed Results and Observations

• Distribution of the Gap:
  • For $n=3$, 10.5% of functions have a gap of 1.
  • For $n=4$, 15.0% of functions have a gap of 1.
  • For $n=5$ (sampled), ~14.4% have a gap of 1.
  • The fraction of gap-1 functions appears stable around 15% for larger $n$.
• Structural Types of Gap-1 Functions:
  • Type A (Decomposable): The function has a non-trivial tree decomposition where sharing saves 1 gate. (Dominant type, ~69-91% of cases).
  • Type B (Tree-Incompatible): All non-trivial tree decompositions are suboptimal by 2 or more gates. Only the trivial $1 \land f$ decomposition works for the formula. These are typically XOR-based structures requiring dual-polarity reuse.
• Input Count vs. Mechanism:
  • At $n \le 4$, only Dual-Polarity sharing is observed (CSE requires 5 distinct inputs).
  • At $n \ge 5$, CSE sharing appears, though Dual-Polarity remains dominant (~68% at $n=6$).
• Tropical Interpretation:
  • The paper reframes the problem using tropical algebra. The tree size is the fixed point of a min-plus operator. The circuit size is this fixed point corrected by a quantized "DAG correction" of 0 or 1.

5. Significance and Impact

1. Structural Completeness: The paper provides a complete structural characterization of sharing in optimal AIGs. It proves that sharing is not a complex, distributed phenomenon but an atomic event involving exactly one gate.
2. Logic Synthesis Implications: Since modern tools (like ABC) optimize AIGs via local rewriting, this result suggests that finding the global optimum often requires a specific "non-local" move (introducing a shared gate) that local heuristics might miss. It explains why some functions get stuck at $opt+1$ (local minima) during synthesis.
3. Limitations of Generalization: The results are specific to the AIG basis with free inversions. The paper notes that bases without free constants or with different gate types (e.g., Majority, XOR-AND) may exhibit larger, unbounded gaps.
4. Open Questions:
   • Does the ~15% fraction of gap-1 functions converge to a limit as $n \to \infty$?
   • Can these structural insights be extended to multi-output circuits?
   • How do these results translate to bases with explicit NOT gates?

Conclusion

The paper demonstrates that in the AIG basis, the advantage of circuits over formulas is strictly bounded and structurally simple. The "gap" is never more than 1, and it is caused by exactly one shared gate operating in either dual-polarity or same-polarity mode. This finding transforms the understanding of Boolean circuit optimization from a search for complex sharing patterns to a search for specific, atomic reconvergence points.