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.
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.
Fixed a few typos.
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.
