<p>There are cases where the symmetries of a problem ( seem to ) characterize its complexity. One very interesting example is constraint satisfaction problems (CSPs).</p>
<p><strong>Definition of CSP</strong></p>
<p>A CSP is given by a domain <span class="math-container">$U$</span>, and a constraint language <span class="math-container">$\Gamma$</span> (<span class="math-container">$k$</span>-ary functions from <span class="math-container">$U^k$</span> to <span class="math-container">$\{0, 1\}$</span>). A constraint satisfaction instance is given by a set of variables <span class="math-container">$V$</span> and constraints from <span class="math-container">$\Gamma$</span>. A solution to the instance is an assignment <span class="math-container">$\phi:V \rightarrow U$</span> such that all constraints are satisfied.</p>
<p>For example, in this language 3-SAT is given by <span class="math-container">$\Gamma$</span> which is the set of all disjunctions of 3 literals, <span class="math-container">$U$</span> is simply <span class="math-container">$\{0, 1\}$</span>. For another example, systems of linear equations mod 2 are given by a <span class="math-container">$\Gamma$</span> which is all linear equations mod 2 with <span class="math-container">$k$</span> variables, and <span class="math-container">$U$</span> is again <span class="math-container">$\{0, 1\}$</span>.</p>
<p><strong>Polymorphisms</strong></p>
<p>There is a sense in which the hardness of a CSP is characterized by its symmetries. The symmetries in question are called polymorphisms. A polymorphism is a way to <em>locally</em> combine several solutions to a CSP to get a new solution. Locally here means that there is a function that  is applied to each variable separately. More precisely, if you have several solutions (satisfying assignments) <span class="math-container">$\phi_1, \ldots, \phi_t$</span>, a polymorphism is a function <span class="math-container">$f:U^t \rightarrow U$</span> that can be applied to each variable to get a new solution <span class="math-container">$\phi$</span>: <span class="math-container">$\phi(v) = f(\phi_1(v), \ldots, \phi_t(v))$</span>. For <span class="math-container">$f$</span> to be a polymorphism it should map all tuples of <span class="math-container">$t$</span> satisfying assignments to any instance to a satisfying assignment of the same instance.</p>
<p>A polymorphism for systems of linear equations for example is <span class="math-container">$f(x, y, z) = x + y + z \pmod 2$</span>. Notice that <span class="math-container">$f(x, x, y) = f(y, x, x) = y$</span>. An <span class="math-container">$f$</span> that satisfies this property is known as a Maltsev operation. CSPs that have a Maltsev polymorphism are solvable by Gaussian elimination.</p>
<p>On the other hand, disjunctions of 3 literals only have dictators as polymorphisms, i.e. functions of the type <span class="math-container">$f(x, y) = x$</span>.</p>
<p><strong>Polymorphisms and Complexity (the dichotomy conjecture)</strong></p>
<p>Polymorphisms in fact have computational implications: if a CSP <span class="math-container">$\Gamma_1$</span> admits all polymorphisms of <span class="math-container">$\Gamma_2$</span>, then <span class="math-container">$\Gamma_1$</span> is polynomial-time reducible to <span class="math-container">$\Gamma_2$</span>. This is a way to formally say that a CSP <span class="math-container">$\Gamma_2$</span> which is &quot;less symmetric&quot; than another CSP <span class="math-container">$\Gamma_1$</span> is in fact harder.</p>
<p>A major open problem in complexity theory is to characterize the hardness of CSPs. The dichotomy conjecture of Feder and Vardi states that any CSP is either in P or NP-complete. The conjecture can be reduced to a statement about polymorphisms: a CSP is NP-hard if and only if the only polymorphisms it admits are &quot;dictators&quot; (otherwise it is in P). I.e. a CSP is hard only if there is no local way to form genuine new solutions from old solutions. The if part (hardness) is known, but the only if part (designing a polytime algorithm) is open.</p>
<p>However, an important case where we do have a dichotomy is boolean CSPs (where <span class="math-container">$U = \{0, 1\}$</span>). According to <a href="https://en.wikipedia.org/wiki/Schaefer%27s_dichotomy_theorem" rel="nofollow noreferrer">Schaefer's theorem</a>, a boolean CSP is in P if it admits one of 6 polymorphisms, otherwise it is NP-complete. The six polymorphisms are basically what you need to solve the problem either by gaussian elimination or by propagation (as you do with horn-sat for example), or to solve it by a trivial assignment.</p>
<p>To read more about polymorphisms, universal algebra, and the dichotomy conjecture, you can look at the <a href="https://doi.org/10.1007/978-3-642-20712-9_26" rel="nofollow noreferrer">survey by Bulatov</a>.</p>
<p><strong>Polymorphisms and Approximability</strong></p>
<p>I also recommend an <a href="https://www.ias.edu/video/csdm/complexityconstraint" rel="nofollow noreferrer">IAS lecture by Prasad Raghavendra</a> where he puts his <a href="https://web.archive.org/web/20130517024031/http://www.cc.gatech.edu/fac/praghave/Files/extabstract.pdf" rel="nofollow noreferrer">result</a> giving optimal approximability of any CSP assuming the unique games conjecture in a similar framework. On a high level, if all polymorphisms (this needs to be generalized to handle approximation problems) of a CSP are close to dictators, one can use the CSP to design a way to test if a function is a dictator, and that turns out to be all you need in order to give a hardness of approximation reduction from unique games. This gives the hardness direction of his result; the algorithmic direction is that when a CSP has a polymorphism which is far from a dictator, one can use an invariance principle (generalization of central limit theorems) to argue that an SDP rounding algorithm gives a good approximation. A really sketchy intuition for the algorithmic part: a polymorphism that is far from a dictator doesn't care if it is given as arguments (a distribution over) variable assignments or gaussian random variables that locally approximate a distribution over variable assignments. This is the same way that a sum function &quot;doesn't care&quot; if it is given discrete  random variables with small variance or gaussian r.v.'s with the same variance, by the central limit theorem. The gaussian random variables we need can be computed from an SDP relaxation of the CSP problem. So we find a polymorphism that is far from a dictator, feed it the gaussian samples, and get a good solution back.</p>

CC BY-SA 3.0
2012-08-30T15:11:19.077Z
Bulatov also gave an invited [talk](http://logic.pdmi.ras.ru/csr2011/node/55) about his survey at CSR 2011.
Tyson Williams
CC BY-SA 4.0
2012-08-30T03:18:32.423Z
2023-05-28T16:35:21.483Z
2023-05-28T16:35:21.483Z
Sasho Nikolov
<p>In the case of determinant, Gaussian elimination can indeed be seen as equivalent to the idea that the determinant has a large symmetry group (of a particular form) <em>and</em> is characterized by that symmetry group (meaning any other homogeneous degree $n$ polynomial in $n^2$ variables with those symmetries must be a scalar multiple of the determinant). (And, as to @Tsuyoshi Ito's point that the symmetries of the permanent seem not to help compute it efficiently: although the permanent is also characterized by its symmetries, its symmetry group is much smaller than that of the determinant.)</p>

<p>You can find a write-up of this - where the symmetries of the determinant are used to do Gaussian elimination, along the way proving that the determinant is characterized by its symmetries - in Proposition 3.4.3 of <a href="http://www.cs.toronto.edu/~jgrochow/grochow-thesis.pdf" rel="nofollow noreferrer">my thesis</a> (shameless self plug - but also, I've never seen it phrased quite this way before and written in full detail, as the OP was asking for, though I'm sure it's been done; I'd be happy if someone had other references).</p>

<p>As to the idea that symmetry always leads to complexity reduction (or not), in addition to things already in the comments, see <a href="https://cstheory.stackexchange.com/questions/871/relationship-between-symmetry-and-computational-intractability/879#879">this question</a> and its answers.</p>

<p>An interesting point is that in Valiant's first papers on what is now known as Valiant's version of algebraic complexity theory, he was trying to make the point that one reason the determinant is important computationally is because roughly all the (then) known efficient algorithms could be reduced to linear algebra and thence to the computation of the determinant, e.g. the FKT algorithm for counting matchings in planar graphs. This is of course an exaggeration, but continues to be borne out by research into holographic algorithms, which often reduce to computing the Pfaffian (a close relative of the determinant). Surely Valiant knew this was an exaggeration, but here's the exact quote just to make sure I'm not misrepresenting (<a href="http://dx.doi.org/10.1145/800135.804419" rel="nofollow noreferrer">L. Valiant. Completeness classes in algebra. ACM STOC 1979</a>):</p>

<blockquote>
  <p>Our main conclusions can be summarized roughly as follows:</p>
  
  <p>(a) Linear algebra offers essentially the only fast technique for computing multivariate polynomials of moderate degree</p>
  
  <p>(b) ...</p>
</blockquote>

CC BY-SA 3.0
2012-08-31T00:13:33.237Z
2012-10-12T21:36:14.937Z
2017-04-13T12:32:28.167Z
Joshua Grochow
<p>Gaussian elimination makes determinant of a matrix polynomial-time computable.   The reduction of complexity in computing the determinant, which is otherwise sum of exponential terms, is due to presence of alternate negative signs (lack of which makes computing permanent is $ \#P\mbox{-}hard$ ie. harder then $NP\mbox{-}C$ problems). This leads to some sort of symmetry in determinant, eg exchange of a pair of rows or columns just reverses the signs. I read somewhere, probably in connections with holographic algorithms introduced by Valiant, that Gaussian elimination could be explained in terms of group action and this in turns leads to generic techniques in complexity reduction.</p>

<p>Also, i feel that almost all source of complexity reduction for any computational problem is some sort of symmetry present. Is it true? Can we rigorously formalize this in terms of group theory?</p>

<p><strong>Edit</strong> </p>

<p>I found the <a href="http://arxiv.org/abs/0910.2443">reference</a>. (pg 2, last line of second paragraph). I did not understand the paper properly, If my question is based on wrong understanding of the paper, please correct me.</p>

CC BY-SA 3.0
2012-08-28T14:37:24.710Z
My personal take on the second paragraph: Problems of wide interest often have symmetry, whether they have efficient algorithms or not.  But other than that, I do not see the truth in your feeling that “almost all source of complexity reduction for any computational problem is some sort of symmetry present.”  For example, I fail to see what symmetry Kruskal’s algorithm uses.  Moreover, the view that efficient algorithms arise from symmetry in problems does not seem to explain why the symmetry of the permanent apparently does not help computing it efficiently.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-28T14:37:52.430Z
No, symmetry does not always lower complexity.  Every interesting question about groups is undecidable.  Sorting is not.
Jeffε
CC BY-SA 3.0
2012-08-28T14:50:56.910Z
"symmetry" is a critical concept which of course has wide application but apparently not so far an overarching theory; maybe there is a way to rephrase this as a question of interest to the group. fyi maybe something to look into, the NP isomorphism conjecture by hartmanis posits a remarkable/strong symmetry in NP complete problems however it is thought to be false.
vzn
CC BY-SA 3.0
2012-08-28T16:37:17.393Z
Is there any common definition of symmetry in TCS? I don't see it here http://en.wikipedia.org/wiki/Symmetry, then I assume that the most rigorous definition we can get for symmetry is exactly the algebrical one: http://en.wikipedia.org/wiki/Symmetry_in_mathematics. Then, it is somehow tautological to ask if "Can we rigorously formalize this in terms of group theory?", because, to ask if "almost all source of complexity reduction for any computational problem is some sort of symmetry present", would exactly mean that a group action would be present.
Immanuel Weihnachten
CC BY-SA 3.0
2012-08-28T17:40:05.103Z
the closest formal statement in this direction that comes to mind is the algebraic dichotomy conjecture, which (to put it very vaguely) states that a CSP is in P if and only if there are nontrivial ways to combine two solutions into a genuinely different third solution. one example is solving a linear system mod 2, which is solvable by gaussian elimination, and where two different solutions determine an affine subspace of solutions
Sasho Nikolov
CC BY-SA 3.0
2012-08-28T17:43:11.073Z
also the variant of the dichotomy conjecture for counting CSP solutions is mostly solved. I guess I will write up an answer once I have more time to dig up the references.
Sasho Nikolov
CC BY-SA 3.0
2012-08-29T02:46:22.710Z
@SashoNikolov [Here](http://arxiv.org/abs/1111.2384) is the reference for the #CSP dichotomy. The main open problem that remains is to prove that the dichotomy is decidable.
Tyson Williams
CC BY-SA 3.0
2012-08-29T02:49:53.020Z
@DurgaDatta I am unaware of a description of Gaussian elimination in terms of a group action resulting from holographic algorithms. Do you think you could find this reference?
Tyson Williams
CC BY-SA 3.0
2012-08-29T07:53:46.440Z
@TysonWilliams I have added the reference in the original question.
DurgaDatta
CC BY-SA 3.0
2012-08-29T18:07:41.833Z
Both the Perm vs Det conjecture and holographic algorithms are both from Valiant, but I don't think they are related.
Tyson Williams
CC BY-SA 3.0
2012-08-29T18:37:05.433Z
ah so what you're actually talking about is GCT, which starts from the idea that the permanent vs. determinant problem can be understood in terms of (roughly) the symmetries under which the two functions are invariant.
Sasho Nikolov
CC BY-SA 3.0
2012-08-29T23:56:38.900Z
There are lots of reasons why a problem admits an efficient algorithm. Convexity, sub-modularity, etc. Symmetries cause case explosion in some combinatorial problems and are sometimes viewed as a source of inefficiency.
Vijay D
CC BY-SA 3.0
2012-08-30T05:07:34.970Z
[corss-posted](http://math.stackexchange.com/q/187822/) on [math.se].
Kaveh
CC BY-SA 3.0
2012-08-30T05:08:10.867Z
It appears that you have crossposted this question *simultaneously*. While we don't mind a question being reposted, our [site policy](http://meta.cstheory.stackexchange.com/a/231/) only permits a repost after sufficient time has passed and you have not obtained the desired answer elsewhere. I am closing the question since simultaneous crossposting duplicates effort and fractures discussion. Please wait a few days and then if your question is still not answered request a reopening by flagging the question for moderator attention (after summarizing relevant discussions from other sites).
Kaveh
CC BY-SA 3.0
2012-08-30T05:17:59.057Z
@Kaveh Sorry for that. I will remove the post there. I think better forum for this question is this. I will take care of these matter in future. Thank you.
DurgaDatta
<cc.complexity-theory><time-complexity><algebraic-complexity><gr.group-theory><determinant>
Gaussian Elimination in terms of Group Action
DurgaDatta
# Gaussian Elimination in terms of Group Action

(Asked by: username_0 on 2012-08-28)

Gaussian elimination makes determinant of a matrix polynomial-time computable. The reduction of complexity in computing the determinant, which is otherwise sum of exponential terms, is due to presence of alternate negative signs (lack of which makes computing permanent is $ \#P\mbox{-}hard$ ie. harder then $NP\mbox{-}C$ problems). This leads to some sort of symmetry in determinant, eg exchange of a pair of rows or columns just reverses the signs. I read somewhere, probably in connections with holographic algorithms introduced by Valiant, that Gaussian elimination could be explained in terms of group action and this in turns leads to generic techniques in complexity reduction.

Also, i feel that almost all source of complexity reduction for any computational problem is some sort of symmetry present. Is it true? Can we rigorously formalize this in terms of group theory?

**Edit**

I found the [reference](http://arxiv.org/abs/0910.2443). (pg 2, last line of second paragraph). I did not understand the paper properly, If my question is based on wrong understanding of the paper, please correct me.

**Tags:** cc.complexity-theory, time-complexity, algebraic-complexity, gr.group-theory, determinant
> **Comments:**
> **username_1**: My personal take on the second paragraph: Problems of wide interest often have symmetry, whether they have efficient algorithms or not.  But other than that, I do not see the truth in your feeling that “almost all source of complexity reduction for any computational problem is some sort of symmetry present.”  For example, I fail to see what symmetry Kruskal’s algorithm uses.  Moreover, the view that efficient algorithms arise from symmetry in problems does not seem to explain why the symmetry of the permanent apparently does not help computing it efficiently.  
> **username_2**: No, symmetry does not always lower complexity.  Every interesting question about groups is undecidable.  Sorting is not.  
> **username_3**: "symmetry" is a critical concept which of course has wide application but apparently not so far an overarching theory; maybe there is a way to rephrase this as a question of interest to the group. fyi maybe something to look into, the NP isomorphism conjecture by hartmanis posits a remarkable/strong symmetry in NP complete problems however it is thought to be false.  
> **username_4**: Is there any common definition of symmetry in TCS? I don't see it here http://en.wikipedia.org/wiki/Symmetry, then I assume that the most rigorous definition we can get for symmetry is exactly the algebrical one: http://en.wikipedia.org/wiki/Symmetry_in_mathematics. Then, it is somehow tautological to ask if "Can we rigorously formalize this in terms of group theory?", because, to ask if "almost all source of complexity reduction for any computational problem is some sort of symmetry present", would exactly mean that a group action would be present.  
> **username_5**: the closest formal statement in this direction that comes to mind is the algebraic dichotomy conjecture, which (to put it very vaguely) states that a CSP is in P if and only if there are nontrivial ways to combine two solutions into a genuinely different third solution. one example is solving a linear system mod 2, which is solvable by gaussian elimination, and where two different solutions determine an affine subspace of solutions  
> **username_5**: also the variant of the dichotomy conjecture for counting CSP solutions is mostly solved. I guess I will write up an answer once I have more time to dig up the references.  
> **username_6**: @SashoNikolov [Here](http://arxiv.org/abs/1111.2384) is the reference for the #CSP dichotomy. The main open problem that remains is to prove that the dichotomy is decidable.  
> **username_6**: @DurgaDatta I am unaware of a description of Gaussian elimination in terms of a group action resulting from holographic algorithms. Do you think you could find this reference?  
> **username_0**: @TysonWilliams I have added the reference in the original question.  
> **username_6**: Both the Perm vs Det conjecture and holographic algorithms are both from Valiant, but I don't think they are related.  
> **username_5**: ah so what you're actually talking about is GCT, which starts from the idea that the permanent vs. determinant problem can be understood in terms of (roughly) the symmetries under which the two functions are invariant.  
> **username_7**: There are lots of reasons why a problem admits an efficient algorithm. Convexity, sub-modularity, etc. Symmetries cause case explosion in some combinatorial problems and are sometimes viewed as a source of inefficiency.  
> **username_8**: [corss-posted](http://math.stackexchange.com/q/187822/) on [math.se].  
> **username_8**: It appears that you have crossposted this question *simultaneously*. While we don't mind a question being reposted, our [site policy](http://meta.cstheory.stackexchange.com/a/231/) only permits a repost after sufficient time has passed and you have not obtained the desired answer elsewhere. I am closing the question since simultaneous crossposting duplicates effort and fractures discussion. Please wait a few days and then if your question is still not answered request a reopening by flagging the question for moderator attention (after summarizing relevant discussions from other sites).  
> **username_0**: @Kaveh Sorry for that. I will remove the post there. I think better forum for this question is this. I will take care of these matter in future. Thank you.  

---

## 2 answers

### Answer by username_9 on 2012-08-31. Score: 13 | Accepted answer

In the case of determinant, Gaussian elimination can indeed be seen as equivalent to the idea that the determinant has a large symmetry group (of a particular form) *and* is characterized by that symmetry group (meaning any other homogeneous degree $n$ polynomial in $n^2$ variables with those symmetries must be a scalar multiple of the determinant). (And, as to @Tsuyoshi Ito's point that the symmetries of the permanent seem not to help compute it efficiently: although the permanent is also characterized by its symmetries, its symmetry group is much smaller than that of the determinant.)

You can find a write-up of this - where the symmetries of the determinant are used to do Gaussian elimination, along the way proving that the determinant is characterized by its symmetries - in Proposition 3.4.3 of [my thesis](http://www.cs.toronto.edu/~jgrochow/grochow-thesis.pdf) (shameless self plug - but also, I've never seen it phrased quite this way before and written in full detail, as the OP was asking for, though I'm sure it's been done; I'd be happy if someone had other references).

As to the idea that symmetry always leads to complexity reduction (or not), in addition to things already in the comments, see [this question](https://cstheory.stackexchange.com/questions/871/relationship-between-symmetry-and-computational-intractability/879#879) and its answers.

An interesting point is that in Valiant's first papers on what is now known as Valiant's version of algebraic complexity theory, he was trying to make the point that one reason the determinant is important computationally is because roughly all the (then) known efficient algorithms could be reduced to linear algebra and thence to the computation of the determinant, e.g. the FKT algorithm for counting matchings in planar graphs. This is of course an exaggeration, but continues to be borne out by research into holographic algorithms, which often reduce to computing the Pfaffian (a close relative of the determinant). Surely Valiant knew this was an exaggeration, but here's the exact quote just to make sure I'm not misrepresenting ([L. Valiant. Completeness classes in algebra. ACM STOC 1979](http://dx.doi.org/10.1145/800135.804419)):

> Our main conclusions can be summarized roughly as follows:
>
> (a) Linear algebra offers essentially the only fast technique for computing multivariate polynomials of moderate degree
>
> (b) ...


---

### Answer by username_5 on 2012-08-30. Score: 8

There are cases where the symmetries of a problem ( seem to ) characterize its complexity. One very interesting example is constraint satisfaction problems (CSPs).

**Definition of CSP**

A CSP is given by a domain $U$, and a constraint language $\Gamma$ ($k$-ary functions from $U^k$ to $\{0, 1\}$). A constraint satisfaction instance is given by a set of variables $V$ and constraints from $\Gamma$. A solution to the instance is an assignment $\phi:V \rightarrow U$ such that all constraints are satisfied.

For example, in this language 3-SAT is given by $\Gamma$ which is the set of all disjunctions of 3 literals, $U$ is simply $\{0, 1\}$. For another example, systems of linear equations mod 2 are given by a $\Gamma$ which is all linear equations mod 2 with $k$ variables, and $U$ is again $\{0, 1\}$.

**Polymorphisms**

There is a sense in which the hardness of a CSP is characterized by its symmetries. The symmetries in question are called polymorphisms. A polymorphism is a way to *locally* combine several solutions to a CSP to get a new solution. Locally here means that there is a function that is applied to each variable separately. More precisely, if you have several solutions (satisfying assignments) $\phi\_1, \ldots, \phi\_t$, a polymorphism is a function $f:U^t \rightarrow U$ that can be applied to each variable to get a new solution $\phi$: $\phi(v) = f(\phi\_1(v), \ldots, \phi\_t(v))$. For $f$ to be a polymorphism it should map all tuples of $t$ satisfying assignments to any instance to a satisfying assignment of the same instance.

A polymorphism for systems of linear equations for example is $f(x, y, z) = x + y + z \pmod 2$. Notice that $f(x, x, y) = f(y, x, x) = y$. An $f$ that satisfies this property is known as a Maltsev operation. CSPs that have a Maltsev polymorphism are solvable by Gaussian elimination.

On the other hand, disjunctions of 3 literals only have dictators as polymorphisms, i.e. functions of the type $f(x, y) = x$.

**Polymorphisms and Complexity (the dichotomy conjecture)**

Polymorphisms in fact have computational implications: if a CSP $\Gamma\_1$ admits all polymorphisms of $\Gamma\_2$, then $\Gamma\_1$ is polynomial-time reducible to $\Gamma\_2$. This is a way to formally say that a CSP $\Gamma\_2$ which is "less symmetric" than another CSP $\Gamma\_1$ is in fact harder.

A major open problem in complexity theory is to characterize the hardness of CSPs. The dichotomy conjecture of Feder and Vardi states that any CSP is either in P or NP-complete. The conjecture can be reduced to a statement about polymorphisms: a CSP is NP-hard if and only if the only polymorphisms it admits are "dictators" (otherwise it is in P). I.e. a CSP is hard only if there is no local way to form genuine new solutions from old solutions. The if part (hardness) is known, but the only if part (designing a polytime algorithm) is open.

However, an important case where we do have a dichotomy is boolean CSPs (where $U = \{0, 1\}$). According to [Schaefer's theorem](https://en.wikipedia.org/wiki/Schaefer%27s_dichotomy_theorem), a boolean CSP is in P if it admits one of 6 polymorphisms, otherwise it is NP-complete. The six polymorphisms are basically what you need to solve the problem either by gaussian elimination or by propagation (as you do with horn-sat for example), or to solve it by a trivial assignment.

To read more about polymorphisms, universal algebra, and the dichotomy conjecture, you can look at the [survey by Bulatov](https://doi.org/10.1007/978-3-642-20712-9_26).

**Polymorphisms and Approximability**

I also recommend an [IAS lecture by Prasad Raghavendra](https://www.ias.edu/video/csdm/complexityconstraint) where he puts his [result](https://web.archive.org/web/20130517024031/http://www.cc.gatech.edu/fac/praghave/Files/extabstract.pdf) giving optimal approximability of any CSP assuming the unique games conjecture in a similar framework. On a high level, if all polymorphisms (this needs to be generalized to handle approximation problems) of a CSP are close to dictators, one can use the CSP to design a way to test if a function is a dictator, and that turns out to be all you need in order to give a hardness of approximation reduction from unique games. This gives the hardness direction of his result; the algorithmic direction is that when a CSP has a polymorphism which is far from a dictator, one can use an invariance principle (generalization of central limit theorems) to argue that an SDP rounding algorithm gives a good approximation. A really sketchy intuition for the algorithmic part: a polymorphism that is far from a dictator doesn't care if it is given as arguments (a distribution over) variable assignments or gaussian random variables that locally approximate a distribution over variable assignments. This is the same way that a sum function "doesn't care" if it is given discrete random variables with small variance or gaussian r.v.'s with the same variance, by the central limit theorem. The gaussian random variables we need can be computed from an SDP relaxation of the CSP problem. So we find a polymorphism that is far from a dictator, feed it the gaussian samples, and get a good solution back.

> **Comments:**
> **username_6**: Bulatov also gave an invited [talk](http://logic.pdmi.ras.ru/csr2011/node/55) about his survey at CSR 2011.  

---

