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?


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$ – Jan Johannsen Nov 21 '11 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$ – MCH Nov 16 '11 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$ – Jan Johannsen Nov 17 '11 at 10:59

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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