<p>To use that empirical fact you really want to know whether approximate numbers can give others approximate numbers. But for the exact case, I think there may be a straightforward way to show this is hard. Here's a sketch.</p>

<p>First note that satisfying assignments correspond to independent sets in a graph. I'll use the phrase "S-projections of I(G)" to describe the function mapping $T \subset S$ to the number of independent sets I with $I \cap S = T$. The "k-projections" are the S-projections for all subsets S of V with $|S|=k$.</p>

<p>Proof outline:</p>

<ol>
<li>If 2-projections give 3-projections, they also give k-projections in polytime for each k.</li>
<li>If 2-projections give 4-projections, then the number of independent sets of a graph is in FP, so FP=#P.</li>
</ol>

<p>(1)
Let $k\geq 3$ such that (k-1)-projections give k-projections. Given a graph, its k-projections, and $x_1,...,x_k,v \in G$, we will compute the projections onto ${x_1,...,x_k,v}$.</p>

<p>Define the graph $G'$ by attaching a fresh vertex to v. This can be seen as weighting v. The (k-1)-projections of $G'$ can be computed because we know the k-projections of G. So then we have the k-projections of $G'$. And this gives ${x_1,...,x_k,v}$-projections of G.</p>

<p>(2)
Given a graph, order the edges ${e_1,...,e_m}$ and define $G_k$ to have edges ${e_1,...,e_k}$. The 2-projections of $G_{k+1}$ can be computed from the 4-projections of $G_k$. The number of independent sets in $G_0$ is $2^{|G|}$. Iteratively the 4-projections of G can be computed in polynomial time.</p>

CC BY-SA 2.5
2010-10-12T09:36:45.210Z
I would prefer not to use that empirical fact! I prefer the exact count of course. But incidentally I noticed that fact while trying to determine the exact count.
Giorgio Camerani
CC BY-SA 2.5
2010-10-12T09:48:36.620Z
Thanks for your answer. Yes, it's hard: as you say, a positive answer to this question would imply #P = FP.
Giorgio Camerani
CC BY-SA 2.5
2010-10-12T09:32:02.083Z
2010-10-12T09:32:02.083Z
Colin McQuillan
<p>Some observations, not an answer.</p>

<p>Further to the note to the question, any combination of 3 literals can be expressed in terms of any other combination of literals on the same variables, together with a small number of terms that the oracle can provide.  This follows from looking at the Venn diagram of 3 intersecting sets, and expressing each of the 8 regions in terms of the other regions.  Note that this does not require the formula to be either monotone or 2CNF.</p>

<p>It is also clear that the number of solutions satisfying any 3-literal conjunct can be expressed as the sum of $2^{n-3}$ terms, each of which is either 0 or 1, expressing a particular assignment to all variables.  Each of these can be evaluated in linear time, but there are exponentially many terms to evaluate, so this doesn't satisfy the requirements.</p>

<p>Hence the question is really about whether it is possible to exploit the property of being monotone 2CNF to compress this exponential-size expression to polynomial size.</p>

<p>I tried to look at a simpler question, restricting the oracle to just an advice string with the number of solutions, when the counts for single or pairwise literal combinations are not available.  I cannot see any way to exploit knowledge of the number of solutions to obtain a quick calculation of the number of solutions with respect to any single literal.</p>

<p>Is there something about monotone 2CNF that would allow the number of solutions in $S$ containing $x_1$ to be obtained quickly, if one knew $|S|$?</p>

CC BY-SA 2.5
2010-10-12T01:12:03.610Z
Indeed, the given information needs to be powerful enough to defeat the underlying hardness. It is known that there is no fpras for solutions to monotone 2-SAT unless NP = RP.
mhum
CC BY-SA 2.5
2010-10-12T07:25:46.480Z
@Andras: What here is called "oracle" is just some sort of dictionary $D$. It seems the case that such dictionary $D$ can be constructed incrementally, by updating it each time a new clause is added to $F$. The problem is that, in order to correctly update $D$, I have to answer this question.
Giorgio Camerani
CC BY-SA 2.5
2010-10-12T07:29:33.110Z
@Walter: Yes, I understand that.  My point is that even a much simpler case is not clear: going from the total number of solutions to the number of solutions containing a single literal.
András Salamon
CC BY-SA 2.5
2010-10-12T07:35:54.740Z
@Andras: In order to cope with your simpler case, you still need to know the number of solutions of pairs of literals and also of triplets of literals. Such simpler case is itself part of the process of building the dictionary. I'd like to try to explain it in a more clear manner, but this little space is uncomfortable.
Giorgio Camerani
CC BY-SA 2.5
2010-10-12T07:45:16.287Z
@Andras: The basic idea is the following. You start with the first clause $c_1 = x_1 \lor x_2$. Clearly, you have 3 solutions, 1 of which contains $\lnot x_1$, 1 of which contains $\lnot x_2$, and none of which contains $\lnot x_1 \land \lnot x_2$. Then you go to the next clause. Each time you process a new clause $c_i$, you can have 3 possible cases: either 2 new variables are added, or 1 new variable is added, or 0 new variables are added. Depending on the case, you create a new dictionary using the old one. Note: the last sentence in my previous comment has nothing to do with Fermat's note.
Giorgio Camerani
CC BY-SA 2.5
2010-10-12T07:47:21.400Z
@Andras: Maybe the empirical fact that I've added to the question may shed some light?
Giorgio Camerani
CC BY-SA 2.5
2010-10-12T08:36:05.040Z
@Walter: I understand that one can go from more specific to less specific.  However, the only way to go from less to more specific seems to be via the atoms of the semilattice of expressions generated by $S$, in other words the actual elements in $S$ (conjunctions of literals involving every variable).  The join of two elements in this semilattice is their largest common subexpression, and the top element is the empty expression which stands for every element of $S$.
András Salamon
CC BY-SA 2.5
2010-10-12T08:54:42.420Z
@Walter: put plainly, it seems to me that one can only work "upwards", not downwards.  This is why I asked what was special about Monotone 2CNF that might help, since this reasoning applies to formulas with no restriction on syntax.
András Salamon
CC BY-SA 2.5
2010-10-12T09:08:02.003Z
@Andras: Which is your opinion on the empirical fact above? OK we are on CS Theory, but...I find that fact surprising (I have no clue on why it works), but maybe to someone else it could be rather trivial and well known.
Giorgio Camerani
CC BY-SA 2.5
2010-10-12T10:57:42.007Z
@András: regarding going from the total number of solutions to the number of solutions containing a single literal. This is hard for general CNF, but perhaps it is not hard for monotone CNF.
Colin McQuillan
CC BY-SA 2.5
2010-10-12T12:12:24.433Z
@András, @Colin: Colin anticipated in his above comment what I was about to say. That possible special feature of Monotone-2CNF is precisely what I'm trying to find.
Giorgio Camerani
CC BY-SA 2.5
2010-10-12T13:49:03.577Z
@Walter: the estimate could relate to some combinatorial property of random 3-uniform hypergraphs, maybe even one that M. Fermat would have been able to prove in the space allotted for a comment.  It doesn't sound especially surprising, but my threshold for surprise is pretty high.
András Salamon
CC BY-SA 2.5
2010-10-12T14:01:37.420Z
It could be that your formula is essentially linear: independent sets in a path follow the Fibonacci sequence. One way to see this is that the partition function (1 1; 1 0) has phi as an eigenvalue.
Colin McQuillan
CC BY-SA 2.5
2010-10-15T11:22:05.930Z
I happened to find some slides discussing a more rigorous result: http://www.isid.ac.in/~antar/Talks/Counting-Hard-Core_KBS_slides.pdf (see page 11)
Colin McQuillan
CC BY-SA 2.5
2010-10-11T23:51:16.987Z
2010-10-11T23:51:16.987Z
András Salamon
<p>A Monotone-2CNF formula is a <a href="http://en.wikipedia.org/wiki/Conjunctive_normal_form">CNF</a> formula where each clause is composed by exactly 2 positive literals.</p>

<p>Now, I have a Monotone-2CNF formula $F$. Let $S$ be the set of $F$'s satisfying assignments. I also have an oracle $O$ which is able to give the following information:</p>

<ol>
<li>The cardinality of the set $S$ (i.e. the number of solutions of $F$).</li>
<li>
Given a variable $x$:
<ul>
<li>The number of solutions in $S$ containing the positive literal $x$.</li>
<li>The number of solutions in $S$ containing the negative literal $\lnot x$.</li>
</ul>
</li>
<li>
Given 2 variables $x_1$ and $x_2$:
<ul>
<li>The number of solutions in $S$ containing $x_1 \land x_2$.</li>
<li>The number of solutions in $S$ containing $x_1 \land \lnot x_2$.</li>
<li>The number of solutions in $S$ containing $\lnot x_1 \land x_2$.</li>
<li>The number of solutions in $S$ containing $\lnot x_1 \land \lnot x_2$.</li>
</ul>
</li>
</ol>

<p>Note that the oracle $O$ is "limited": it works only on $F$, it can't be used on a formula $F' \neq F$. <hr></p>

<blockquote>
  <p><strong>Question:</strong></p>
  
  <p>Given 3 variables $x_1$, $x_2$, $x_3$
  is it possible to determine the number
  of solutions in $S$ containing $\lnot
  x_1 \land \lnot x_2 \land \lnot x_3$ in
  polynomial time, using $F$ and
  the information provided by $O$?</p>
  
  <p><strong>Note:</strong></p>
  
  <p>You can replace $\lnot
  x_1 \land \lnot x_2 \land \lnot x_3$ in the
  question with whatever else of the 8 possible
  combinations of $x_1$, $x_2$, $x_3$. The problem
  would remain the same.</p>
</blockquote>

<hr>

<blockquote>
  <p><strong>Empirical fact:</strong></p>
  
  <p>I came across the following empirical fact one
  week ago. Let $S_{\lnot x_1 \land \lnot x_2} \subset S$
  be the set of those solutions containing $\lnot x_1 \land \lnot x_2$,
  and let $S_{\lnot x_1 \land \lnot x_2 \land x_3} \subset S$ be the set
  of those solutions containing $\lnot x_1 \land \lnot x_2 \land x_3$. Now, it
  seems to be the case that, if condition $C$ holds, this relationship also holds:
  <br><br>$\frac{|S_{\lnot x_1 \land \lnot x_2}|}{|S_{\lnot x_1 \land \lnot x_2 \land x_3}|} \simeq \phi$<br><br>
  where $\phi = 1.618033...$ is the golden ratio. Condition $C$ seems to be the following: <i>"$x_1$, $x_2$, $x_3$ are mentioned in $F$ almost the same number of times"</i>.</p>
</blockquote>

CC BY-SA 3.0
2012-01-21T19:46:53.533Z
last I heard 2CNF was in P. is anyone aware of that? doesnt that answer your question?
vzn
CC BY-SA 3.0
2012-03-18T08:43:13.767Z
@vzn: The decision version of 2CNF is in $P$. This is the counting version of the monotone case (given a monotone 2CNF formula $F$, you have to compute __how many__ satisfying assignments it has).
Giorgio Camerani
CC BY-SA 2.5
2010-10-11T09:33:15.673Z
When you say "solutions containing the negative literal -x" -- do you mean "solutions with x=0"?
Noam
CC BY-SA 2.5
2010-10-11T09:42:26.673Z
@Noam: Yes, exactly.
Giorgio Camerani
CC BY-SA 2.5
2010-10-11T10:31:28.913Z
Easy observation: since the number of possible questions to the oracle O is polynomially bounded, without loss of generality you can query all questions at the beginning of an algorithm.  Therefore, we can replace the oracle by additional input, with a promise that those numbers are correct.  I think that this promise formulation is slightly simpler than considering it as an oracle.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-11T12:00:31.497Z
@Tsuyoshi: Yes, I agree with you.
Giorgio Camerani
CC BY-SA 2.5
2010-10-11T13:42:46.770Z
@Tsuyoshi: What I call "oracle" here is actually just some sort of dictionary. But let me say that it should be considered as something "magic" and "unique": what I mean is that it is not possible to propagate $\lnot x_1 \land \lnot x_2 \land \lnot x_3$ on $F$ and then building a similar dictionary on the resulting simplified formula; the answer has to be computed by using only that "magic" information about $F$.
Giorgio Camerani
CC BY-SA 2.5
2010-10-11T14:07:13.450Z
Typically, Monotone-2SAT has other structure than just being "exactly 2-CNF"... did you intend for "monotone" to mean something else?
Ryan Williams
CC BY-SA 2.5
2010-10-11T14:14:53.453Z
@Ryan: With "monotone" I mean "there isn't any negative literal".
Giorgio Camerani
CC BY-SA 2.5
2010-10-11T14:18:42.073Z
@Ryan: I was writing a comment to your answer. I think it was useful, even if it just transformed the problem into an equally-hard one. I'll enrich the question to clarify that.
Giorgio Camerani
CC BY-SA 2.5
2010-10-11T15:59:43.353Z
In your problem, can an algorithm read the formula F?  I had assumed so, but I have just realized that the question suggests otherwise.  If an algorithm cannot read F and it is given only the oracle O, then the question is very different.  In that case, I guess that the answer is not uniquely determined by the information provided by the oracle O, though I do not have a proof right now.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-11T16:36:47.030Z
@Tsuyoshi: You made the correct assumption. The algorithm can read the formula $F$; I've just clarified the question (sorry if it was misleading). I think you're right in saying that, otherwise, the answer is not uniquely determined (I arrived to the same conclusion through a linear system with an insufficient number of equations). Ah, of course the algorithm must have a polynomial running time (this has also been clarified in the question).
Giorgio Camerani
<cc.complexity-theory><ds.algorithms><sat><counting-complexity>
Counting solutions of Monotone-2CNF formulas
Giorgio Camerani
# Counting solutions of Monotone-2CNF formulas

(Asked by: username_0 on 2010-10-11)

A Monotone-2CNF formula is a [CNF](http://en.wikipedia.org/wiki/Conjunctive_normal_form) formula where each clause is composed by exactly 2 positive literals.

Now, I have a Monotone-2CNF formula $F$. Let $S$ be the set of $F$'s satisfying assignments. I also have an oracle $O$ which is able to give the following information:

1. The cardinality of the set $S$ (i.e. the number of solutions of $F$).
2. Given a variable $x$:
   * The number of solutions in $S$ containing the positive literal $x$.
   * The number of solutions in $S$ containing the negative literal $\lnot x$.
3. Given 2 variables $x\_1$ and $x\_2$:
   * The number of solutions in $S$ containing $x\_1 \land x\_2$.
   * The number of solutions in $S$ containing $x\_1 \land \lnot x\_2$.
   * The number of solutions in $S$ containing $\lnot x\_1 \land x\_2$.
   * The number of solutions in $S$ containing $\lnot x\_1 \land \lnot x\_2$.

Note that the oracle $O$ is "limited": it works only on $F$, it can't be used on a formula $F' \neq F$. 

---

> **Question:**
>
> Given 3 variables $x\_1$, $x\_2$, $x\_3$
> is it possible to determine the number
> of solutions in $S$ containing $\lnot
> x\_1 \land \lnot x\_2 \land \lnot x\_3$ in
> polynomial time, using $F$ and
> the information provided by $O$?
>
> **Note:**
>
> You can replace $\lnot
> x\_1 \land \lnot x\_2 \land \lnot x\_3$ in the
> question with whatever else of the 8 possible
> combinations of $x\_1$, $x\_2$, $x\_3$. The problem
> would remain the same.

---

> **Empirical fact:**
>
> I came across the following empirical fact one
> week ago. Let $S\_{\lnot x\_1 \land \lnot x\_2} \subset S$
> be the set of those solutions containing $\lnot x\_1 \land \lnot x\_2$,
> and let $S\_{\lnot x\_1 \land \lnot x\_2 \land x\_3} \subset S$ be the set
> of those solutions containing $\lnot x\_1 \land \lnot x\_2 \land x\_3$. Now, it
> seems to be the case that, if condition $C$ holds, this relationship also holds:
>   
>   
> $\frac{|S\_{\lnot x\_1 \land \lnot x\_2}|}{|S\_{\lnot x\_1 \land \lnot x\_2 \land x\_3}|} \simeq \phi$  
>   
> where $\phi = 1.618033...$ is the golden ratio. Condition $C$ seems to be the following: *"$x\_1$, $x\_2$, $x\_3$ are mentioned in $F$ almost the same number of times"*.

**Tags:** cc.complexity-theory, ds.algorithms, sat, counting-complexity
> **Comments:**
> **username_2**: When you say "solutions containing the negative literal -x" -- do you mean "solutions with x=0"?  
> **username_0**: @Noam: Yes, exactly.  
> **username_3**: Easy observation: since the number of possible questions to the oracle O is polynomially bounded, without loss of generality you can query all questions at the beginning of an algorithm.  Therefore, we can replace the oracle by additional input, with a promise that those numbers are correct.  I think that this promise formulation is slightly simpler than considering it as an oracle.  
> **username_0**: @Tsuyoshi: Yes, I agree with you.  
> **username_0**: @Tsuyoshi: What I call "oracle" here is actually just some sort of dictionary. But let me say that it should be considered as something "magic" and "unique": what I mean is that it is not possible to propagate $\lnot x_1 \land \lnot x_2 \land \lnot x_3$ on $F$ and then building a similar dictionary on the resulting simplified formula; the answer has to be computed by using only that "magic" information about $F$.  
> **username_4**: Typically, Monotone-2SAT has other structure than just being "exactly 2-CNF"... did you intend for "monotone" to mean something else?  
> **username_0**: @Ryan: With "monotone" I mean "there isn't any negative literal".  
> **username_0**: @Ryan: I was writing a comment to your answer. I think it was useful, even if it just transformed the problem into an equally-hard one. I'll enrich the question to clarify that.  
> **username_3**: In your problem, can an algorithm read the formula F?  I had assumed so, but I have just realized that the question suggests otherwise.  If an algorithm cannot read F and it is given only the oracle O, then the question is very different.  In that case, I guess that the answer is not uniquely determined by the information provided by the oracle O, though I do not have a proof right now.  
> **username_0**: @Tsuyoshi: You made the correct assumption. The algorithm can read the formula $F$; I've just clarified the question (sorry if it was misleading). I think you're right in saying that, otherwise, the answer is not uniquely determined (I arrived to the same conclusion through a linear system with an insufficient number of equations). Ah, of course the algorithm must have a polynomial running time (this has also been clarified in the question).  
> **username_1**: last I heard 2CNF was in P. is anyone aware of that? doesnt that answer your question?  
> **username_0**: @vzn: The decision version of 2CNF is in $P$. This is the counting version of the monotone case (given a monotone 2CNF formula $F$, you have to compute __how many__ satisfying assignments it has).  

---

## 2 answers

### Answer by username_5 on 2010-10-12. Score: 6 | Accepted answer

To use that empirical fact you really want to know whether approximate numbers can give others approximate numbers. But for the exact case, I think there may be a straightforward way to show this is hard. Here's a sketch.

First note that satisfying assignments correspond to independent sets in a graph. I'll use the phrase "S-projections of I(G)" to describe the function mapping $T \subset S$ to the number of independent sets I with $I \cap S = T$. The "k-projections" are the S-projections for all subsets S of V with $|S|=k$.

Proof outline:

1. If 2-projections give 3-projections, they also give k-projections in polytime for each k.
2. If 2-projections give 4-projections, then the number of independent sets of a graph is in FP, so FP=#P.

(1)
Let $k\geq 3$ such that (k-1)-projections give k-projections. Given a graph, its k-projections, and $x\_1,...,x\_k,v \in G$, we will compute the projections onto ${x\_1,...,x\_k,v}$.

Define the graph $G'$ by attaching a fresh vertex to v. This can be seen as weighting v. The (k-1)-projections of $G'$ can be computed because we know the k-projections of G. So then we have the k-projections of $G'$. And this gives ${x\_1,...,x\_k,v}$-projections of G.

(2)
Given a graph, order the edges ${e\_1,...,e\_m}$ and define $G\_k$ to have edges ${e\_1,...,e\_k}$. The 2-projections of $G\_{k+1}$ can be computed from the 4-projections of $G\_k$. The number of independent sets in $G\_0$ is $2^{|G|}$. Iteratively the 4-projections of G can be computed in polynomial time.

> **Comments:**
> **username_0**: I would prefer not to use that empirical fact! I prefer the exact count of course. But incidentally I noticed that fact while trying to determine the exact count.  
> **username_0**: Thanks for your answer. Yes, it's hard: as you say, a positive answer to this question would imply #P = FP.  

---

### Answer by username_6 on 2010-10-11. Score: 7

Some observations, not an answer.

Further to the note to the question, any combination of 3 literals can be expressed in terms of any other combination of literals on the same variables, together with a small number of terms that the oracle can provide. This follows from looking at the Venn diagram of 3 intersecting sets, and expressing each of the 8 regions in terms of the other regions. Note that this does not require the formula to be either monotone or 2CNF.

It is also clear that the number of solutions satisfying any 3-literal conjunct can be expressed as the sum of $2^{n-3}$ terms, each of which is either 0 or 1, expressing a particular assignment to all variables. Each of these can be evaluated in linear time, but there are exponentially many terms to evaluate, so this doesn't satisfy the requirements.

Hence the question is really about whether it is possible to exploit the property of being monotone 2CNF to compress this exponential-size expression to polynomial size.

I tried to look at a simpler question, restricting the oracle to just an advice string with the number of solutions, when the counts for single or pairwise literal combinations are not available. I cannot see any way to exploit knowledge of the number of solutions to obtain a quick calculation of the number of solutions with respect to any single literal.

Is there something about monotone 2CNF that would allow the number of solutions in $S$ containing $x\_1$ to be obtained quickly, if one knew $|S|$?

> **Comments:**
> **username_7**: Indeed, the given information needs to be powerful enough to defeat the underlying hardness. It is known that there is no fpras for solutions to monotone 2-SAT unless NP = RP.  
> **username_0**: @Andras: What here is called "oracle" is just some sort of dictionary $D$. It seems the case that such dictionary $D$ can be constructed incrementally, by updating it each time a new clause is added to $F$. The problem is that, in order to correctly update $D$, I have to answer this question.  
> **username_6**: @Walter: Yes, I understand that.  My point is that even a much simpler case is not clear: going from the total number of solutions to the number of solutions containing a single literal.  
> **username_0**: @Andras: In order to cope with your simpler case, you still need to know the number of solutions of pairs of literals and also of triplets of literals. Such simpler case is itself part of the process of building the dictionary. I'd like to try to explain it in a more clear manner, but this little space is uncomfortable.  
> **username_0**: @Andras: The basic idea is the following. You start with the first clause $c_1 = x_1 \lor x_2$. Clearly, you have 3 solutions, 1 of which contains $\lnot x_1$, 1 of which contains $\lnot x_2$, and none of which contains $\lnot x_1 \land \lnot x_2$. Then you go to the next clause. Each time you process a new clause $c_i$, you can have 3 possible cases: either 2 new variables are added, or 1 new variable is added, or 0 new variables are added. Depending on the case, you create a new dictionary using the old one. Note: the last sentence in my previous comment has nothing to do with Fermat's note.  
> **username_0**: @Andras: Maybe the empirical fact that I've added to the question may shed some light?  
> **username_6**: @Walter: I understand that one can go from more specific to less specific.  However, the only way to go from less to more specific seems to be via the atoms of the semilattice of expressions generated by $S$, in other words the actual elements in $S$ (conjunctions of literals involving every variable).  The join of two elements in this semilattice is their largest common subexpression, and the top element is the empty expression which stands for every element of $S$.  
> **username_6**: @Walter: put plainly, it seems to me that one can only work "upwards", not downwards.  This is why I asked what was special about Monotone 2CNF that might help, since this reasoning applies to formulas with no restriction on syntax.  
> **username_0**: @Andras: Which is your opinion on the empirical fact above? OK we are on CS Theory, but...I find that fact surprising (I have no clue on why it works), but maybe to someone else it could be rather trivial and well known.  
> **username_5**: @András: regarding going from the total number of solutions to the number of solutions containing a single literal. This is hard for general CNF, but perhaps it is not hard for monotone CNF.  
> **username_0**: @András, @Colin: Colin anticipated in his above comment what I was about to say. That possible special feature of Monotone-2CNF is precisely what I'm trying to find.  
> **username_6**: @Walter: the estimate could relate to some combinatorial property of random 3-uniform hypergraphs, maybe even one that M. Fermat would have been able to prove in the space allotted for a comment.  It doesn't sound especially surprising, but my threshold for surprise is pretty high.  
> **username_5**: It could be that your formula is essentially linear: independent sets in a path follow the Fibonacci sequence. One way to see this is that the partition function (1 1; 1 0) has phi as an eigenvalue.  
> **username_5**: I happened to find some slides discussing a more rigorous result: http://www.isid.ac.in/~antar/Talks/Counting-Hard-Core_KBS_slides.pdf (see page 11)  

---

