54 Why Naive XOR Expansion Blows Up Exponentially

The exclusive-or function of $x \oplus y = 1$ just if $x \neq = y$ . The/a smallest Boolean formula computing $x \oplus y$ is:

A (x, y) : = (x \land \neg y) \lor (\neg x \land y)

Now consider the Parity function $⨁_{i = 1}^{n} x_{i}$ . One way of defining Boolean formula $A_{n}$ for $⨁_{i = 1}^{n} x_{i}$ is by induction on $n$ as follows:

A_{1} A_{n + 1} : = x_{1} : = (x_{n + 1} \land \neg A_{n}) \lor (\neg x_{n + 1} \land A_{n})

However, notice that this leads to an exponential blowup: $∣ A_{n} ∣ > 2^{n - 1}$

However, we could chose to compute Parity differently, namely by re-bracketing under associativity and commutativity.

Define formulas $B_{n} (x_{1}, \dots, x_{n})$ for $⨁_{i = 1}^{n} x_{i}$ by divide-and-conquer induction on $n$ as follows:

B_{1} (x) B_{2 n} (x, y) B_{2 n} (x, y, z) : = x : = (B_{n} (x) \land \neg B_{n} (y)) \lor (\neg B_{n} (x) \land B_{n} (y)) : = (z \land \neg B_{n} (x, y)) \lor (\neg z \land B_{n} (x, y)))

This construction only leads to a $n^{O (1)}$ -size $O (lo g n)$ -depth family of formulas for parity.

Ayush Acharjya's Notes

Explorer

54 Why Naive XOR Expansion Blows Up Exponentially

Graph View

Backlinks