__
Revision #1 to TR17-146 | 1st October 2017 19:05
__
#### On Derandomized Composition of Boolean Functions

**Abstract:**
The composition of two Boolean functions $f:\left\{0,1\right\}^{m}\to\left\{0,1\right\}$, $g:\left\{0,1\right\}^{n}\to\left\{0,1\right\}$

is the function $f \diamond g$ that takes as inputs $m$ strings $x_{1},\ldots,x_{m}\in\left\{0,1\right\}^{n}$

and computes

\[

(f \diamond g)(x_{1},\ldots,x_{m})=f\left(g(x_{1}),\ldots,g(x_{m})\right).

\]

This operation has been used several times for amplifying different

hardness measures of $f$ and $g$. This comes at a cost: the function

$f \diamond g$ has input length $m\cdot n$ rather than $m$ or $n$, which

is a bottleneck for some applications.

In this paper, we propose to decrease this cost by ``derandomizing''

the composition: instead of feeding into $f \diamond g$ independent inputs

$x_{1},\ldots,x_{m}$, we generate $x_{1},\ldots,x_{m}$ using a shorter

seed. We show that this idea can be realized in the particular setting

of the composition of functions and universal relations.

To this end, we provide two different techniques for achieving such

a derandomization: a technique based on averaging samplers, and a

technique based on Reed-Solomon codes.

**Changes to previous version:**
Fixed a few typos.

__
TR17-146 | 1st October 2017 14:58
__

#### On Derandomized Composition of Boolean Functions

TR17-146
Authors:

Or Meir
Publication: 1st October 2017 19:04

Downloads: 21

Keywords:

**Abstract:**
The composition of two Boolean functions $f:\left\{0,1\right\}^{m}\to\left\{0,1\right\}$, $g:\left\{0,1\right\}^{n}\to\left\{0,1\right\}$

is the function $f \diamond g$ that takes as inputs $m$ strings $x_{1},\ldots,x_{m}\in\left\{0,1\right\}^{n}$

and computes

\[

(f \diamond g)(x_{1},\ldots,x_{m})=f\left(g(x_{1}),\ldots,g(x_{m})\right).

\]

This operation has been used several times for amplifying different

hardness measures of $f$ and $g$. This comes at a cost: the function

$f \diamond g$ has input length $m\cdot n$ rather than $m$ or $n$, which

is a bottleneck for some applications.

In this paper, we propose to decrease this cost by ``derandomizing''

the composition: instead of feeding into $f \diamond g$ independent inputs

$x_{1},\ldots,x_{m}$, we generate $x_{1},\ldots,x_{m}$ using a shorter

seed. We show that this idea can be realized in the particular setting

of the composition of functions and universal relations.

To this end, we provide two different techniques for achieving such

a derandomization: a technique based on averaging samplers, and a

technique based on Reed-Solomon codes.