Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #4 to TR17-146 | 7th May 2019 16:03

#### On Derandomized Composition of Boolean Functions

Revision #4
Authors: Or Meir
Accepted on: 7th May 2019 16:03
Keywords:

Abstract:

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.

Changes to previous version:

Revised following comments from Journal referees.

Revision #3 to TR17-146 | 24th July 2018 17:10

#### On Derandomized Composition of Boolean Functions

Revision #3
Authors: Or Meir
Accepted on: 24th July 2018 17:10
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.

Revision #2 to TR17-146 | 23rd January 2018 19:04

#### On Derandomized Composition of Boolean Functions

Revision #2
Authors: Or Meir
Accepted on: 23rd January 2018 19:04
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:

Small fixes.

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

#### On Derandomized Composition of Boolean Functions

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