<p>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 <a href="http://theory.csail.mit.edu/ftp-data/pub/ftp/tcryptol/old-05.ps">Yao's XOR lemma</a>. 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$.</p>

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

CC BY-SA 3.0
2011-11-16T23:15:10.490Z
To complement this post: XOR lemmas are everywhere. Eg, see this paper and its references: http://theoryofcomputing.org/articles/v004a007/
Mahdi Cheraghchi
CC BY-SA 3.0
2011-11-17T10:59:15.170Z
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.
Jan Johannsen
CC BY-SA 3.0
2011-11-16T18:16:44.527Z
2011-11-16T18:16:44.527Z
mikero
<p>Here's an somewhat relevant example we are currently covering in my class.</p>

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

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

<p>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$.</p>

<p>$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. </p>

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

<p>$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)}$.</p>

<p>This is often called "Andreev's function" in the literature. Hastad <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.9886">proved</a> (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.)</p>

CC BY-SA 3.0
2011-11-21T09:30:42.147Z
Thanks Ryan, that's exactly the kind of thing I was looking for.
Jan Johannsen
CC BY-SA 3.0
2011-11-16T23:53:38.693Z
2011-11-16T23:53:38.693Z
Ryan Williams
<p>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$.  </p>

<p>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:</p>

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

<p>Are there other uses of this technique in other areas?  </p>

<cc.complexity-theory><reference-request><boolean-functions><proof-complexity>
Uses of XORification
Jan Johannsen
# Uses of XORification

(Asked by: username_0 on 2011-11-16)

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?

**Tags:** cc.complexity-theory, reference-request, boolean-functions, proof-complexity


---

## 2 answers

### Answer by username_3 on 2011-11-16. Score: 15 | Accepted answer

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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.9886) (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.)

> **Comments:**
> **username_0**: Thanks Ryan, that's exactly the kind of thing I was looking for.  

---

### Answer by username_1 on 2011-11-16. Score: 13

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](http://theory.csail.mit.edu/ftp-data/pub/ftp/tcryptol/old-05.ps). 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.

> **Comments:**
> **username_2**: To complement this post: XOR lemmas are everywhere. Eg, see this paper and its references: http://theoryofcomputing.org/articles/v004a007/  
> **username_0**: 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.  

---

