13
$\begingroup$

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>

$\endgroup$
1

1 Answer 1

14
$\begingroup$

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.

$\endgroup$
9
  • 8
    $\begingroup$ The software will not let me begin my answer with "Hi Gil," and I am a bit creeped out by this level of micromanagement. $\endgroup$ Sep 4, 2013 at 15:47
  • 2
    $\begingroup$ This is because your answer should not begin with "Hi Gil". It's not a personal e-mail, it's a post on a public website. Of course, the likes of you are not the ones targeted by this; it is rather new users who are not aware of these conventions which the software aims to control. $\endgroup$ Sep 4, 2013 at 15:58
  • 1
    $\begingroup$ My view is that it's fine to acknowledge when one is writing in response to someone else's contribution. This is normal and positive in many online settings. I tried to do so in the briefest possible way, by personal address; don't see anything wrong with that. $\endgroup$ Sep 4, 2013 at 18:56
  • 2
    $\begingroup$ Nice construction! I have a question: let f be the indicator function of L', and h be as in Gil's question. Now, your argument shows that h agrees with f on y's that are legal codewords. But how about y's that are not legal codewords? $\endgroup$
    – Or Meir
    Sep 4, 2013 at 21:58
  • 2
    $\begingroup$ Can you implement such a thing with monotone $f$? $\endgroup$
    – Gil Kalai
    Oct 12, 2013 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.