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 authors give a characterization of strong approximation resistance which I don't completely understand.

Given a measure $\Lambda$ in $R^{k + {k \choose 2}}$, (the coordinates of a point in this space are written $x_1, x_2, ..., x_k, x_{(1,2)}, ... x_{(i,j)}, ... , x_{(k-1, k)}$) and some subset $S \subset [k]$, they define $\Lambda_S$ as the measure projected onto the coordinates of $S$.

I can think of two such interpretations for $\Lambda_S$. First fix $k=4$ so that $\Lambda$ is in $R^{10}$. Our coordinates are $1, 2, 3, 4, (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)$. Fix $S = \{1, 2, 3\}$.

Interpretation 1: Under one interpretation, the measure $\Lambda_S$ should be projected using the coordinates $1$ and $2$ and $3$ only.

Interpretation 2: Under the other interpretation we should also include the "pair" coordinates so we should project using $1$, $2$, $3$, $(1,2)$, $(1,3)$, $(2,3)$.

I'm thinking that the second interpretation is the correct one. This is because the definition is reformulated in terms of matrices in definition 2.11 on page 19. In this formulation, we have a measure $\zeta$ on a subspace of matrices in $R^{(k+1)\times(k+1)}$ analogous to the measure $\Lambda$, but given $S$, projection measure $\zeta_S$ is defined by taking the submatrix formed by restricting to rows and columns whose indices are in $S$. But in this formulation, the entry $i,j$ of the matrix corresponds to the coordinate $x_{(i,j)}$.

Am I correct? Or is there some way to reconcile the first interpretation with the matrix analogue?


1 Answer 1


Section 1 of the paper, in which the first definition appears, is introductory. The formal development starts at Section 2. The part of the paper starting at Section 2 is completely self-contained. Therefore, if there is any mismatch between a definition in Section 1 and a definition elsewhere, the latter is the correct one.

In theoretical computer science, papers are published in conferences. Conference reviewers cannot be expected to read 50-page strong manuscripts, and so the argument has to be described in an elaborate introduction. This is why there is so much technical content in Section 1. The development there is simplified and more leisurely to facilitate reading. The authoritative part of the paper is Section 2 and forward.


Your Answer

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

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