Simple Circuit Extensions for XOR in PTIME

Resolving the $\mathrm{𝖭𝖯}$-hardness of $\mathrm{𝖬𝖢𝖲𝖯}$ using standard reductions implies breakthrough complexity lower bounds that, while believed to be true, seem far beyond current techniques. Kabanets and Cai showed that a “natural” reduction from $\mathrm{𝖲𝖠𝖳}$ to $\mathrm{𝖬𝖢𝖲𝖯}$ can be used to construct functions in $𝖤$ with super-polynomial circuit complexity [24]. Natural reductions suffice for nearly all known $\mathrm{𝖭𝖯}$-hardness results; they generalize textbook-style gadget reductions. Later, Murray and Williams showed that a polynomial-time many-one reduction from $\mathrm{𝖲𝖠𝖳}$ to $\mathrm{𝖬𝖢𝖲𝖯}$ implies $\mathrm{𝖤𝖷𝖯}\ne \mathrm{𝖹𝖯𝖯}$ [34]. These types of barriers use the efficiency and/or structure of an assumed reduction $R$ from $\mathrm{𝖲𝖠𝖳}$ to $\mathrm{𝖬𝖢𝖲𝖯}$ to bound the circuit complexity of truth tables printed by $R$ and obtain dramatic consequences.

We can avoid these barriers by aiming instead for ETH-hardness of $\mathrm{𝖬𝖢𝖲𝖯}$, because hardness proofs under the Exponential Time Hypothesis allow for super-polynomial time reductions. Supposing that $\mathrm{𝖬𝖢𝖲𝖯}$ is ETH-hard under a reduction $R^{\prime }$ gives only a sub-exponential time bound on $R^{\prime }$, which may well be super-polynomial. Inspecting the arguments of Kabanets and Cai, natural super-polynomial time reductions from $\mathrm{𝖲𝖠𝖳}$ to $\mathrm{𝖬𝖢𝖲𝖯}$ imply only linear circuit lower bounds – which are known via gate elimination! Similarly, a key step in Murray and Williams’ argument fails when the many-one reduction requires super-polynomial time. Thus, [24, 34] and similar barriers do not apply to proving ETH-hardness of $\mathrm{𝖬𝖢𝖲𝖯}$ by reducing an ETH-hard problem to $f$-Simple Extension.

More barriers to $\mathrm{𝖭𝖯}$-hardness of $\mathrm{𝖬𝖢𝖲𝖯}$ were established by considering either the reduction, the $\mathrm{𝖬𝖢𝖲𝖯}$ problem, or both relative to an oracle. For example, oracle-independent reductions work for ${\mathrm{𝖬𝖢𝖲𝖯}}^A$ for every oracle $A$; often they use $\mathrm{𝖬𝖢𝖲𝖯}$ only to distinguish between “high” and “low” complexity functions and arise in arguments about pseudorandomness. Hirahara and Watanabe showed that if $\mathrm{𝖬𝖢𝖲𝖯}$ is $\mathrm{𝖭𝖯}$-hard under efficient deterministic oracle-independent reductions, then $𝖯=\mathrm{𝖭𝖯}$ – so it is natural to conjecture that such reductions are impossible [15]. Later, Ren and Santhanam showed that the complexity of $\mathrm{𝖬𝖢𝖲𝖯}$ is not robust in relativized worlds [39]. This suggests that non-relativizing techniques will be required to prove the correctness of a reduction from $\mathrm{𝖲𝖠𝖳}$ to $\mathrm{𝖬𝖢𝖲𝖯}$.

We conjecture that aiming for ETH-hardness of $\mathrm{𝖬𝖢𝖲𝖯}$ via $f$-Simple Extension avoids these barriers by combining gate elimination with the circuit complexity of a specific and explicit function: $f$. Ren and Santhanam comment that it remains unclear whether relativization is a barrier to the techniques in some recent work in meta-complexity that used gate elimination and related ideas [17, 18, 19, 21] (see Section 1, pg. 2 of [39]). Indeed, many gate elimination arguments prove non-relativizing statements. For example, relativizing DeMorgan circuits to ${\mathrm{𝖷𝖮𝖱}}_2$ falsifies the lower bounds on $\mathrm{𝖷𝖮𝖱}$. Furthermore, the characterization of a function’s optimal circuits seems unlikely to be robust to the addition of oracle gates – avoiding oracle-independence.

A breakthrough result of Hirahara shows that Partial $\mathrm{𝖬𝖢𝖲𝖯}$ is unconditionally $\mathrm{𝖭𝖯}$-hard under randomized reductions [12]. Extending this result could yield $\mathrm{𝖭𝖯}$-hardness of total-function $\mathrm{𝖬𝖢𝖲𝖯}$. However, that approach faces a version of the oracle-independence barrier: Hirahara’s reduction is in fact many-one and oracle-independent! If there is a many-one oracle-independent randomized reduction from $\mathrm{𝖲𝖠𝖳}$ to $\mathrm{𝖬𝖢𝖲𝖯}$, then the polynomial hierarchy ($\mathrm{𝖯𝖧}$) collapses [15]. Because $\mathrm{𝖯𝖧}$ is widely conjectured to be infinite and strict, it seems that significantly new ideas would be required to extend Hirahara’s argument about ${\mathrm{𝖬𝖢𝖲𝖯}}^{\ast }$ to show $\mathrm{𝖭𝖯}$-hardness of total $\mathrm{𝖬𝖢𝖲𝖯}$.

Knowing the lower-bounds of some explicit Boolean functions $f$, a natural question to ask is: What about the structure of every optimal circuit computing $f$? For some functions and bases, this is easy to answer: minimal Red’kin circuits for ${\mathrm{𝖮𝖱}}_n$ are binary trees of $\vee$ gates. For even slightly more complex functions, structural characterization seems to require intricate and exhaustive case analysis. Some of the earliest work on this question include [41] and [4] which investigated when optimal circuits for certain $2$-output Boolean functions must compute each output independently. More recently, Kombarov extended the characterization of $\mathrm{𝖷𝖮𝖱}$ circuits to other complete bases when NOT-gates are counted [27].

Both $ℛ$ and $𝒟$ are compatible with Ilango’s proof of ETH-hardness of ${\mathrm{𝖬𝖢𝖲𝖯}}^{\ast }$. That proof relied on functions whose optimal $\{\wedge ,\vee ,\neg \}$-circuits are read-once monotone formulas. There it was irrelevant whether $\neg$ gates contribute to size: those circuits simply did not contain negations. However, when we move to more complex functions like $\mathrm{𝖷𝖮𝖱}$, negations must appear in the optimal circuits and as such, we must decide how to treat them.

In the search for non-linear circuit lower bounds, the choice between ${\mu }_R$ and ${\mu }_D$ is largely irrelevant: the two complexity measures the same up to a small constant factor. However, as we discuss in Section 2, Ilango’s technique requires knowledge of the structure of optimal circuits. In this setting, there is not necessarily as strong connection between the two bases. By extending Kombarov’s characterization of $\mathrm{𝖷𝖮𝖱}$ circuits in $ℛ$ to $𝒟$, we show for that particular function, optimal circuits are structurally similar in both bases. But, for other functions, this may well not be the case. Negations could enable a function’s optimal circuits to greatly vary under the two complexity measures. Indeed, negations can greatly increase a problems complexity: [3] showed that a Boolean function learning problem became difficult only once the number of $\neg$ gates exceeded a small threshold.

By considering both bases in this work, we limit how negations impact the complexity of $f\text{-}\mathrm{𝖲𝖤𝖯}$. We show that they do not greatly increase the complexity of the simple extensions themselves: in Section 4.1, we explain how simple extensions under both complexity measures are highly structured. If a future hardness reduction relies on negations, their role will be in increasing the structural complexity of the underlying base function, either by increasing the number of distinct optimal circuits, or by enabling non-constant fan-out in a base circuit.

To prove $f\text{-}\mathrm{𝖲𝖤𝖯}$ is ETH-hard we will need a Boolean function whose optimal circuits are more complex and/or varied than $\mathrm{𝖷𝖮𝖱}$. Specifically, these circuits must either (1) be superlinear in size, (2) require non-constant fanout, or (3) be sufficiently numerous. Superlinear bounds seem beyond current techniques – the most fruitful of which, gate elimination, seems unlikely to be able to prove lower bounds above even $11n$ for wide classes of functions [9]. As such, it seems more sensible to identify Boolean functions which violate the latter conditions. However, structural characterization of the optimal circuits is also hard, and seems to require very tight circuit complexity bounds. Indeed, our DeMorgan basis characterization of $\mathrm{𝖷𝖮𝖱}$ repeatedly exploited Schnorr’s exact $3(n-1)$ bound for ${\mathrm{𝖷𝖮𝖱}}_n$ [42]. This greatly narrows the prospective class of functions from the original specification: “more complex than read-once formulas.”

Observe that every function besides $\mathrm{𝖷𝖮𝖱}$ in the table has a (small) gap between the circuit lower and upper bound, and the “$\mathrm{\Omega }(1)$ Fanout” column ends with a question mark (?). This is because $\mathrm{𝖷𝖮𝖱}$ is the only listed function for which we know the exact circuit complexity and an optimal circuit characterization. The other “$\mathrm{\Omega }(1)$ Fanout” entries above are extrapolated by assuming that their respective DeMorgan upper bound constructions are optimal. For instance, Zwick conjectured that optimal circuits computing the Sum Mod 4 (${\mathrm{𝖬𝖮𝖣}}_4$) function are “shaped like” ternary full-adder blocks [46]. If this conjecture is true, then ${\mathrm{𝖬𝖮𝖣}}_4$-Simple Extension can be solved in $\mathrm{𝗉𝗈𝗅𝗒}$-time since such circuits satisfy the properties of our Main Lemma. Since the ${\mathrm{𝖬𝖮𝖣}}_{2^k}$ functions are computed similarly, we conjecture that exactly characterizing the optimal circuits for Zwick’s functions would yield efficient Simple Extension Solvers – not a proof of ETH-hardness for total $\mathrm{𝖬𝖢𝖲𝖯}$.

However, we do have linear lower bounds for functions whose best known constructions have non-constant fanout: the multiplexing function ($\mathrm{𝖬𝖴𝖷}$) contains sub-circuits which are reused a logarithmic number of times [25]. In contrast to $\mathrm{𝖷𝖮𝖱}$ however, the bounds for $\mathrm{𝖬𝖴𝖷}$ are not tight. The best lower bound is $2(n-1)$, given by Paul [35].

The most obvious next step is to either (1) obtain total characterization of the Multiplexer or (2) extend our Simple Extension Solver to handle circuits with super-constant fanout. Neither of these tasks seems easy, but also they have not been subject to intensive research the way that super-linear circuit lower bounds and hardness of $\mathrm{𝖬𝖢𝖲𝖯}$ have. We hope that connecting these kinds of results to ETH-hardness of $\mathrm{𝖬𝖢𝖲𝖯}$ provides new perspective and motivation.

Ilango’s ${\mathrm{𝖬𝖢𝖲𝖯}}^{\ast }$ result has also formed the basis for several hardness results in other models of computation such as formulas and branching programs [20, 7, 8]; could one show that the simple extension problem for formulas or branching programs is hard? These other models of computations may prove easier to work with than unrestricted circuits. They also enjoy superlinear lower bounds thereby bypassing our algorithm. Investigating the simple extension problem in these settings would provide insight into the feasibility of the approach in the circuit setting.

We conclude this section with a discussion of the simple extension problem in general. Despite having only been studied as a tool for proving hardness of $\mathrm{𝖬𝖢𝖲𝖯}$ thus far, it may be of independent interest. For example, while hardness of time-bounded Kolmogorov complexity is tightly connected to the existence of one-way functions, hardness of $\mathrm{𝖬𝖢𝖲𝖯}$ has much weaker quantitative connections [29, 38]. The $f$-Simple Extension Problem is more “structured” than $\mathrm{𝖬𝖢𝖲𝖯}$ and easily reduces to it, so hardness assumptions about $f$-Simple Extension Problem are stronger. Could such assumptions imply one-way functions?

To encode $\mathrm{𝖡𝖯𝖨𝖲}$ in $\widehat{f}\text{-}{\mathrm{𝖲𝖤𝖯}}^{\ast }$, we first prove two lemmas which were essentially proven in tandem in [19] as Lemma 16. We separate them out here and stay faithful to the original arguments. Like Lemma 16, these lemmas establish structural properties of circuits computing our base function $\widehat{f}$ and our eventual output $\widehat{g}$.

In particular, the only difference between two distinct optimal circuits for $\widehat{f}$ is which binary tree of fanin 2 $\vee$ gates is used.

Observe that $\psi$ must read all of its input variables and furthermore must do so positively. This is because (1) $f$ depends on all of its variables and is monotone in them, and (2) $\psi$ is normalized and thus no $\neg$ gates can appear internally in the circuit. We note that $\psi$ must use a total of $4n-1$ gates since $f$ is non-degenerate on $4n$ variables computable. We see that $\psi$ must contain at least $2n-1$ $\vee$ gates: substituting $z=1^{2n}$ and simplifying yields a monotone read once formula computing ${\mathrm{𝖮𝖱}}_{2n}(y_1,\mathrm{\dots },y_{2n})$ which must consist of $2n-1$ $\vee$ gates that appear in $\psi$.

We now argue that each $z_i$ feeds into an $\wedge$ gate. Assume otherwise, then observe that setting $z_i=1$ and simplifying removes at least two gates (since $z_1\vee p\equiv 1\vee p\equiv 1)$. The resulting read once formula for ${\widehat{f}|}_{z_i\leftarrow 1}$ uses at most $4n-3$ gates. This is a contradiction since ${\widehat{f}|}_{z_i\leftarrow 1}$ still depends on all of its remaining $4n-1$ variables: it cannot be computed by a circuit with fewer than $4n-2$ gates.

We now argue the other input to the $\wedge$ gate fed by $z_i$ is $y_i$. Assume otherwise. Notice that since $\psi$ is read-once, setting $z_i\leftarrow 0$ simplifying disconnects the other input to $\wedge$ gate and thus removes dependence on any variables it depends on. However, ${\widehat{f}|}_{z_i\leftarrow 0}$ still depends on all of its variables besides $y_i$. Thus the $\wedge$ gate can only read $y_i$.

Since each $z_i$ and $y_i$ feed a distinct $\wedge$ gate, there are at least $2n$ $\wedge$ gates. Since there are $4n-1$ total gates, and at least $2n-1$ $\vee$ gates, we know that these $\wedge$ gates are the only $\wedge$ gates that appear. Thus the remainder of the circuit is a binary tree of $2n-1$ $\vee$ gates whose $2n$ leaves are the $2n$ $\wedge$ gates. $◀$

Having established the structure of optimal circuits computing $\widehat{f}$ we can further restrict its simple extensions. Extra restrictions to the truth table enforce that extension variables must be spliced into the circuit using $2n$ additional $\vee$ gates that each read a different $y_i$. This pairing of each $y_i$ with a different $x_j$ will define a permutation in which we can encode $\mathrm{𝖡𝖯𝖨𝖲}$ solutions.

Since $g(x,y,z)=\widehat{f}(y,z)$ when $x=0^{2n}$, we know that $\varphi$ must read all $y$ and $z$ variables positively. Similarly, all $x$ variables must be read positively, since $g(x,y,1^{2n})={\mathrm{𝖮𝖱}}_{4n}(x_1,\mathrm{\dots }{x}_{2n},y_1,\mathrm{\dots }{y}_{2n})$. Note that these restrictions also imply that $\varphi$ contains exactly $4n-1$ $\vee$ gates and $2n$ $\wedge$ gates since substituting and simplifying yields optimal formulas for those restrictions. From the lemma above, we know that when setting $x=0^{2n}$ and simplifying, we obtain a circuit structurally equivalent to ${\bigvee }_{i\in [2n]}(y_i\wedge z_i)$. Therefore $2n$ $\vee$ gates must be removed during simplification. These $\vee$ gates cannot feed any remaining $\vee$ above the $\wedge$ gates, since otherwise setting $x=1^{2n}$ would fix the circuit to be $1$, rather than ${\mathrm{𝖮𝖱}}_{2n}(z_1,\mathrm{\dots }{z}_{2n})$. Similarly, $z_i$ cannot feed any of these $\vee$ gates, as setting $x=1^{2n}$ would remove dependence on that $z_i$ since the circuit is a read-once formula. Thus each $\vee$ gate can only depend on the $x$ and $y$ variables. Observe that each $y_i$ must feed into one of these $\vee$ gates instead of the $\wedge$ gate fed by $z_i$, as otherwise when we set $x=1^{2n}$, the function would still depend on $y_i$. Since there are exactly $2n$ additional $\vee$ gates, and exactly $2n$ $y$ and $2n$ $x$ variables, its easy to see that each additional $\vee$ gate must read one $x_i$ and one $y_j$. Therefore, as a formula, $\varphi$ must be ${\bigvee }_{i\in [2n]}((x_{\pi (i)\vee y_i})\wedge z_i)$ for some permutation $\pi$. $◀$

We now provide an explicit reduction from $\mathrm{𝖡𝖯𝖨𝖲}$ to $\widehat{f}\text{-}{\mathrm{𝖲𝖤𝖯}}^{\ast }$. Given an instance $G$ of $\mathrm{𝖡𝖯𝖨𝖲}$ we output $4n$ and the partial truth-table for a function $\widehat{g}$ that is consistent with the requirements of Lemma 4. We add three additional restrictions (listed in Table 2) to ensure that any permutation $\pi$, whose corresponding circuit $C_{\pi }\equiv {\bigvee }_{i\in [2n]}\left((x_{\pi (i)}\vee y_i)\wedge z_i\right)$ is consistent with $\widehat{g}$, is also a solution for $G$ (and vice versa). All other rows of the truth table are left undefined (e.g. as $\star$). We summarize the requirements for any valid $\mathrm{𝖡𝖯𝖨𝖲}$ solution $\sigma$, the corresponding restriction, and how it enforces the requirement on $\pi$ in Table 2.

This completes the reduction as any $\sigma$ satisfying $\mathrm{𝖡𝖯𝖨𝖲}$ for $G$ can be used to construct a read-once circuit consistent with $\widehat{g}$ and vice versa. The arguments verifying this are the same as in [19], and we refer the reader there for the full details.

In its introduction, [19] identifies $\widehat{g}$ as a simple extension of ${\mathrm{𝖮𝖱}}_{4n}$. Under this lens, the hardness comes from determining which ${\mathrm{𝖮𝖱}}_{4n}$ base circuit can have the $z$ extension variables added. The additional truth-table restrictions on $\widehat{g}$ force each $z_i$ to be spliced in a particular way adjacent to $y_i$. Assuming ETH, there are $\mathrm{\Omega }(n!)$ optimal base ${\mathrm{𝖮𝖱}}_{4n}$ circuits that must be checked via brute-force.

From both presentations, we see that leveraging $f\text{-}\mathrm{𝖲𝖤𝖯}$ involves explicit circuit size lower bounds. Indeed, both Lemma 3 and Lemma 4 prove formula lower bounds for specific non-degenerate functions. However, in a sense, circuit lower bounds are intrinsic to the reduction itself. This connection can be made rigorous: the reduction can used to produce explicit Boolean functions which enjoy non-vacuous lower bounds. On no instance of $\mathrm{𝖡𝖯𝖨𝖲}$, the reduction outputs a partial truth table where every completion is non-degenerate but not a simple extension. Hence, the circuit complexity of these completions is not the vacuous $6n-1$ lower bound obtained by knowing that functions produced are non-degenerate.

Furthermore, the reduction did not solely rely on the circuit complexity of $\widehat{f}$ and $\widehat{g}$. Lemmas 3 and 4 tightly control how base circuits and their extensions can be arranged; and this is pivotal for encoding $\mathrm{𝖡𝖯𝖨𝖲}$ permutations. This structural requirement can be formalized by observing the reduction is also an efficient Levin reduction.

Recall, from [33], that a Levin reduction is a many-one reduction that also efficiently maps witnesses, not just problem instances. More precisely, let $R$ be a set of ordered pairs $(x,w)$ where $x$ is a yes-instance of a problem and $w$ is an accompanying certificate. We define $L_R$, the language defined by $R$, to be the set of elements $x$ such that $(x,w)\in R$ for some $w$. Then a Levin reduction between two languages $A$ and $B$ is an efficient many-one reduction $r$ between problem instances paired with two efficient mappings $m,\mathrm{\ell }$ between instance-witness pairs that satisfy (1) if $(x,w)\in R_A$ then $(r(x),m(x,w))\in R_B$ and (2) $(t(x),w)\in R_B$ implies $(x,\mathrm{\ell }(x,w))\in R_A$.

For $\mathrm{𝖡𝖯𝖨𝖲}$, the witnesses for an instance are simply the valid permutations $\sigma$ and witnesses for $\widehat{f}\text{-}\mathrm{𝖲𝖤𝖯}$ are optimal circuits computing the extension. Let ${ℛ}_{\mathrm{𝖡𝖯𝖨𝖲}}$ and ${ℛ}_{\widehat{f}\text{-}{\mathrm{𝖲𝖤𝖯}}^{\ast }}$ be the sets of ordered pairs consisting of problem instances and all of their witnesses as described. The reduction admits linear time mappings between witnesses: given $\sigma$, simply construct ${\bigvee }_{i\in [2n]}((x_{\sigma (i)}\vee y_i)\wedge z_i)$ and given a circuit for $\widehat{g}$, simply read off the permutation from the $x$ variables.