The (block-)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.

Revised following comments from Journal referees.

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.

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.

Small fixes.

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.

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.

Fixed a few typos.

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.

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.