6
$\begingroup$

We say that a Boolean function $f : \{0, 1\}^n \rightarrow \{0, 1\}$ is helpful for another Boolean function $g$ if $f(x)$ can be computed with a smaller circuit given $g(x)$ as an extra input bit. I'm curious about questions like "What is the probability that $f$ is helpful for $g$ given that $g$ is helpful for $f$, where $f, g$ are distributed uniformly randomly?" Another way to phrase this question is "Is the helpful relation mostly directed?"

Just to get the intuition across, one simple example of this is parity, where if you're computing the parity of the bits indexed by elements of some set $S$, $\chi_S$, then $\chi_T$ will only be helpful when the set of extra indices you have to compute parity on to correct this to $\chi_S$ is less than $|S|$. Specifically, we have to compute parity on $S - T$, $T - S$, then add these to $\chi_T(x)$, so if $|S \triangle T| < |S|$, $\chi_T$ is helpful for $\chi_S$.

I'm sure this has been looked at before, so I'm mostly looking for references here. One can define a similar, stronger notion, where you define $Inner(f)$ to be the set of functions computed by an internal node to a size-optimal circuit for $f$. For parity it seems that most of the internal functions are parity functions on less inputs. What other functions, which are not some easily recoverable distortion of parity on a subset of the bits, are helpful for parity?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.