XORification is the technique to make a Boolean function or formula harder by replacing every variable $x$ by the XOR of $k\geq 2$ distinct variables $x_1 \oplus \ldots \oplus x_k$.

I am aware of uses of this technique in proof complexity, mainly to obtain space lower bounds for resolution-based proof systems, e.g., in the papers:

  • Eli Ben-Sasson. Size space tradeoffs for resolution. STOC 2002, 457-464.
  • Eli Ben-Sasson and Jakob Nordström. Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions. ICS 2011, 401-416.

Are there other uses of this technique in other areas?


2 Answers 2


Here's an somewhat relevant example we are currently covering in my class.

The "storage access function" is defined on $2^k+k$ bits as:

$SA(x_1,...,x_{2^k}, a_1,...,a_k) = x_{bin(a_1 \cdots a_k)}$

where $bin(a_1 \cdots a_k)$ is the unique integer in $\{1,\ldots,2^k\}$ corresponding to the string $a_1 \cdots a_k$.

$SA$ has formulas of size about $O(k \cdot 2^k)$ over AND/OR/NOT: have $2^k$ groups of all possible $k$-ANDs over the $a_i$ variables, so that exactly one group outputs $1$ on every input. Then AND each bit $x_i$ with the output of the corresponding group, then OR all of these outputs.

However, the following "SA of XOR" function, on $2^{k+1}$ inputs, requires about $2^{3k}$-size formulas over AND/OR/NOT:

$SA(x_1,...,x_{2^k}, \bigoplus_{j=1}^{2^k/k} a_{1,j},..., \bigoplus_{j=1}^{2^k/k} a_{k,j}) = x_{bin(a_1 \cdots a_k)}$.

This is often called "Andreev's function" in the literature. Hastad proved (improving a component of Andreev's argument) that cubic-size formulas are essentially necessary. (It is not hard to find nearly cubic-size formulas for it, too.)

  • $\begingroup$ Thanks Ryan, that's exactly the kind of thing I was looking for. $\endgroup$ Nov 21, 2011 at 9:30

This might be a slight reach, but the idea of XOR'ing a bunch of things to make a task "harder" shows up in cryptography. It first appeared in the guise of Yao's XOR lemma. If $X$ is a slightly unpredictable random variable, then $Y = X_1 \oplus X_2 \oplus \cdots \oplus X_k$ is extremely unpredictable if $k$ is large enough, where the $X_i$'s are independent draws of $X$.

Nowadays, this technique is quite standard in crypto, typically for amplifying a weak construction (commitment scheme, oblivious transfer protocol, etc) into a strong one.

  • 5
    $\begingroup$ To complement this post: XOR lemmas are everywhere. Eg, see this paper and its references: theoryofcomputing.org/articles/v004a007 $\endgroup$ Nov 16, 2011 at 23:15
  • 2
    $\begingroup$ The XOR lemma is different from what I look for: here a $k$-ary parity gate is added at the output, with $k$ copies of the function fed into it. XORification on the other hand adds a $k$-ary parity gate at each input, with $k$ new variables fed into it. $\endgroup$ Nov 17, 2011 at 10:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.