Hardness of noisy Boolean functions

Question

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>

Answer 1

for Question 1, the answer is Yes, and can be shown as follows. (I will also be implicitly sketching an affirmative answer to Q4, since the argument is uniform and will treat all input lengths at once.)

Fix any NP-complete language $L$, and a family of good binary error-correcting codes (with rate 1/4 and correcting from a .1 fraction of errors, say). Let $Enc_n: \{0, 1\}^n \rightarrow \{0, 1\}^{4n}$ be the encoding function for length $n$; we use some such code where $Enc = \{Enc_n\}$ is computable by a uniform polynomial-time algorithm.

Define $L'$ as the set of strings $z$ that are within distance at most $.05 |z|$ from a codeword $y \in Enc(L)$ encoding some element of $L$. Note that $L'$ is in NP, as you can guess and check the nearby codeword, the decoded word, and the NP certificate for the decoded word's membership in $L$.

Then the claim is that any "approximation" of $L'$ in your sense is NP-hard for $\varepsilon = .01$. For if we consider a valid codeword $y = Enc(x)$ of some length $4n$, then with probability $1 - o(1)$ over a random $\varepsilon$-perturbed version $y'$ of $y$, it will disagree with $y$ in at most a .05 fraction of coordinates, and will therefore disagree with any other codeword of $Enc_n$ in a more than $.05$ fraction of coords. For such $y'$ we have $y' \in L'$ iff $x \in L$. So if $h$ is any approximation to the $\varepsilon$-smoothed version of $L'$ in your sense, then we must have $h(y) = L(x)$. As $Enc$ is efficiently computable, this gives us a way to efficiently reduce membership questions for $L$ to ones for $h$. So $h$ is NP-hard.

Two notes:

(1) error-correcting encodings of NP instances have been used before in several papers, notably
D. Sivakumar: On Membership Comparable Sets. J. Comput. Syst. Sci. 59(2): 270-280 (1999).

(2) the argument above of course says nothing about the average-case complexity of any NP problem, since error-correction is being applied on an instance-by-instance basis.