6
$\begingroup$

I'm reading a paper about Constraint Satisfaction Problems, specifically "A Characterization of Strong Approximation Resistance", Subhash Khot, Madhur Tulsiani, Pratik Worah (ECCC TR13-075).

The following sentence appears in the third paragraph of the very first page:

"... the fraction of satisfied constraints is at least $\rho(f) + \Omega(1)$"

At the bottom of page two we have a similar notation where GapCSP(f)$_{1-o(1), \rho(f) + o(1)}$ is defined.

It is confusing for me where the "limit" is being taken here. Put another way, what is the number that's varying inside the asymptotic notation?

I would think that maybe the limit is taken as the number of constraints goes to infinity, but the paper specifically mentions that fixed instances of CSP can have a fraction of $1 - o(1)$ constraints satisfied. But what values could be varying within a fixed instance? (page 2 paragraph 2)

Improve this question
$\endgroup$
2
  • $\begingroup$ For future reference, please add a full reference to the paper (e.g., title, authors, where published), not just a link. This serves two purposes: (1) it increases the chances that others can find this question using search, so it's more likely to be of benefit to others, not just you; (2) if the link dies, we still have a way to uniquely identify the paper. I've done it for you this time, but just letting you know so you can do it yourself in the future. $\endgroup$
    – D.W. ♦
    Commented Oct 13, 2014 at 1:43
  • $\begingroup$ Noted, thanks for adding the information for me. $\endgroup$
    – Mark
    Commented Oct 13, 2014 at 5:34

1 Answer 1

Reset to default
3
$\begingroup$

In general, when you see big-O notation in algorithms, the default assumption is that the number that's varying is the size of the input. Here the input size is $n+m$.

In this case the claim is valid if you think of it in terms of $m$, the number of constraints.

The claim that is being made here is a very basic claim. It's basically a consequence of the fact that $\text{Var}[X] \to 0$ as $m \to \infty$, where the random variable $X$ is the fraction of constraints satisfied by a random assignment. (Heuristically, if you were willing to assume independence, it would follow from the Central Limit Theorem. In this case, you cannot assume independence, but a similar result follows nonetheless.)

If you are not sure how to prove this claim, or were unable to recognize this as a fairly standard concentration result, then you're probably going to find the rest of the paper very difficult going, and you might need to start by reading more basic textbooks and papers before diving into this paper.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks for your answer and formatting suggestions. The quote fragment from the paper is not a claim, but a definition. I interpret your answer to mean that the random assignment algorithm satisfies $f(\rho) + \Omega(1)$ fraction of the clauses in expectation. Also, is it correct to use Big O notation to talk about specific instances of problems? I think your interpretation makes sense, but only when applied to the set of all possible instances as a whole - in contrast to the usage of the authors of the paper. $\endgroup$
    – Mark
    Commented Oct 13, 2014 at 5:31
  • $\begingroup$ The fact that a random assignment satisfies $f(\rho) + \Omega(1)$ of the constraints in expectation should follow a fortiori from the fact that a random assignment satisfies $f(\rho)$ constraints in expectation using linearity of expectation. Maybe you are saying something more about the distribution of $X$, but how this relates to the Big O notation, I'm still unsure. $\endgroup$
    – Mark
    Commented Oct 13, 2014 at 5:42
  • 1
    $\begingroup$ @Mark, The expectation is as you say. The range of likely values comes from the variance, using a concentration result (e.g., a random variable $X$ is in the range $[\mu-10 \sigma,\mu+10\sigma]$ almost certainly, where $\mu$ is the expectation and $\sigma$ the standard deviation). $\endgroup$
    – D.W. ♦
    Commented Oct 13, 2014 at 8:28
  • 1
    $\begingroup$ @Mark, I don't know why you say that it's a definition not a claim. The statement that with high probability the fraction of constraints satisfied is in the range $[\rho(f)-o(1),\rho(f)+o(1)]$ sure sounds like a claim to me, not a definition. Anyway, either way, it doesn't really change the answer to your question. A random assignment satisfies exactly $\rho(f)$ in expectation, not $\rho(f)+\Omega(1)$. I don't see anything wrong with the paper's use of Big-O notation here. What did you think was wrong with it? $\endgroup$
    – D.W. ♦
    Commented Oct 13, 2014 at 8:31
  • $\begingroup$ Ah thanks, I thought you were talking about the quote from my question which comes from page 1. And yes the expectation is $\rho(f)$; I was confusing $\Omega$ with $O$. $\endgroup$
    – Mark
    Commented Oct 13, 2014 at 14:57

Your Answer

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

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