Let $f$ be a Boolean function  of $n$ Boolean variables. Let $g(x)=T_\epsilon (f) (x)$ be the expected value of $f(y)$ when $y$ is obtained from $x$ by flipping each coordinate with probability $\epsilon/2$.I am interested in cases where it is computationally hard to approximate $g$. Let me fixed a notion of approximation (but there may be others): A Boolean function $h$ approximates $g$ if $h(x)=1$ when $g(x)\ge 0.9$ and $h(x)=0 $ when $g(x)\le 0.1$.A counting argument (based on the existence of positive rate error correcting codes) seem to give that there are Boolean functions for which any such approximation requires an exponential size circuit. But the question is what happens when $f$ to start with is in NP or in its neighborhood. Q1: Is there an example of $f$ described by NP circuit (or P-space) so that every $h$ is NP hard, or hard in some weaker sense.To see that $h$ might not always be easy (I thank Johan Hastad for useful discussion about it) we can consider the property of graphs of having a clique of size $n^{1/4}$, for random input, it is conceivable that it is hard to detect if there is a large clique but this is manifested by having more than expected cliques of size log n in the noisy graph. In this case any $h$ will be likely-hard (but not provably, and not terribly hard as quasi-polynomial circuits will be telling).Q2: What is the situation if $f$ to start with is low complexity. ($AC^0$, monotone $TC^0$, $ACC$ etc.)Q3: What is the situation for some basic examples of Boolean functions. (The question can be extended also to real-valued function.)Q4: Can the above question be asked formally for the uniform (Turing-machine) model of computation?Update: In view of Andy's answer (Hi there, Andy) I think that the most interesting question is to understand the situation for various specific functions.Update Another question Q5 [Q1 for monotone functions] (also in view of Andy's answer). What is the situation if $f$ is monotone? Can we still encode robustly an NP complete questions>
Hardness of noisy Boolean functions
cc.complexity theory;circuit complexity;boolean functions