Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR17-146 | 1st October 2017 19:05

On Derandomized Composition of Boolean Functions

RSS-Feed




Revision #1
Authors: Or Meir
Accepted on: 1st October 2017 19:05
Downloads: 143
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.



Changes to previous version:

Fixed a few typos.


Paper:

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.



ISSN 1433-8092 | Imprint