Name
Abstract | ||
|---|---|---|
The (block-)composition of two Boolean functions
$$f :
\{0, 1\}^{m} \rightarrow \{0, 1\}, g : \{0, 1\}^{n} \rightarrow \{0, 1\}$$
is the function
$$f \diamond g$$
that takes as
inputs m strings
$$x_{1}, \ldots , x_{m} \in \{0, 1\}^{n}$$
and computes
$$(f \diamond g)(x_{1}, \ldots , x_{m}) = f (g(x_{1}), \ldots , g(x_{m})).$$
This operation has been used several times in the past 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 (Gavinsky et al. in SIAM J Comput 46(1):114–131, 2017; Karchmer et al. in Computat Complex 5(3/4):191–204, 1995b). 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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/s00037-019-00188-1 | computational complexity |
Keywords | Field | DocType |
Circuit complexity, circuit lower bounds, formula complexity, formula lower bounds, derandomization, communication complexity, Karchmer–Wigderson relations, KRW conjecture, 68Q15 | Boolean function,Discrete mathematics,Combinatorics,Boolean expression,Mathematics | Journal |
Volume | Issue | ISSN |
28 | 4 | 1016-3328 |
Citations | PageRank | References |
0 | 0.34 | 18 |
Authors | ||
1 | ||