<p>This theorem from that paper of Sinclair and Jerrum is slightly stronger than the sentence quoted in the question, and gives the fpras mentioned by Dyer:</p>

<blockquote>
  <p>THEOREM 4.6. Let $R\subseteq \Sigma^*\times\Sigma^*$ be self-reducible. If there exists a polynomially time-bounded randomised approximate counter for $R$ within
  ratio $1 + O(n^\alpha)$ for some $\alpha\in\mathbb R$, then there exists a fully polynomial randomised approximation scheme for $\#R$.</p>
</blockquote>

<p>Note the quantification over $R$. Your first question asks if "counting self-reducible structures might have an FPRAS", but this theorem is looking at particular $R$'s and showing that if $R$ has a weak kind of approximation algorithm, then $R$ also has a stronger kind of approximation algorithm.</p>

<p>Jerrum and Sinclair explain it like this:</p>

<blockquote>
  <p>The chief significance of Theorem 4.6 is that it establishes a notion of
  approximate counting which is robust with respect to polynomial time
  computation, at least for the large class of self-reducible relations [...] We suggest that this notion will be useful in the future classification
  of hard counting problems [...]</p>
</blockquote>

CC BY-SA 3.0
2015-02-19T03:13:29.247Z
Two small questions. What type of self-reducibility are we talking about here? Randomised self-reducibility? And second, any more specific ideas for question 2? Thanks in advance
Paramar
CC BY-SA 3.0
2015-02-20T07:32:30.533Z
Check out Sinclair and Jerrum's paper (http://www.cs.berkeley.edu/~sinclair/approx.pdf) for the definition of self-reducibility, informal (p.94) and formal (p.99). It's quite different from randomised self-reducibility. For question 2 - I believe the theorem I quoted is the "indirect" general result being referred to.
Colin McQuillan
CC BY-SA 3.0
2015-02-13T07:34:22.100Z
2015-02-13T07:34:22.100Z
Colin McQuillan
<p>I am quoting a phrase of Martin Dyer in his paper Approximate Counting by Dynamic Programming:</p>

<p><strong>Since 0-1 knapsack is self-reducible, existence of an fpras for the problem now follows indirectly from a general result of Sinclair and Jerrum[19]</strong> </p>

<p>In that paper of Sinclair and Jerrum it is stated that:  </p>

<p><strong>It follows that, for self-reducible structures, polynomial time
randomised algorithms for counting to within factors of the form (1 +$n^{-\beta}$) are
available either for all $\beta \in R$ or for no $\beta \in R$.</strong></p>

<p>Question 1: Does statement 2 mean that counting self reducible structures might have an FPRAS?</p>

<p>Question 2: What is the indirect method Dyer is talking about? Is it some folklore method considered well known?</p>

<ds.algorithms><counting-complexity><randomized-algorithms>
FPRAS on #P complete problems and self reducibility
Paramar
# FPRAS on #P complete problems and self reducibility

(Asked by: username_0 on 2015-02-12)

I am quoting a phrase of Martin Dyer in his paper Approximate Counting by Dynamic Programming:

**Since 0-1 knapsack is self-reducible, existence of an fpras for the problem now follows indirectly from a general result of Sinclair and Jerrum[19]**

In that paper of Sinclair and Jerrum it is stated that:

**It follows that, for self-reducible structures, polynomial time
randomised algorithms for counting to within factors of the form (1 +$n^{-\beta}$) are
available either for all $\beta \in R$ or for no $\beta \in R$.**

Question 1: Does statement 2 mean that counting self reducible structures might have an FPRAS?

Question 2: What is the indirect method Dyer is talking about? Is it some folklore method considered well known?

**Tags:** ds.algorithms, counting-complexity, randomized-algorithms

---

## 1 answers

### Answer by username_1 on 2015-02-13. Score: 3 | Accepted answer

This theorem from that paper of Sinclair and Jerrum is slightly stronger than the sentence quoted in the question, and gives the fpras mentioned by Dyer:

> THEOREM 4.6. Let $R\subseteq \Sigma^\*\times\Sigma^\*$ be self-reducible. If there exists a polynomially time-bounded randomised approximate counter for $R$ within
> ratio $1 + O(n^\alpha)$ for some $\alpha\in\mathbb R$, then there exists a fully polynomial randomised approximation scheme for $\#R$.

Note the quantification over $R$. Your first question asks if "counting self-reducible structures might have an FPRAS", but this theorem is looking at particular $R$'s and showing that if $R$ has a weak kind of approximation algorithm, then $R$ also has a stronger kind of approximation algorithm.

Jerrum and Sinclair explain it like this:

> The chief significance of Theorem 4.6 is that it establishes a notion of
> approximate counting which is robust with respect to polynomial time
> computation, at least for the large class of self-reducible relations [...] We suggest that this notion will be useful in the future classification
> of hard counting problems [...]

> **Comments:**
> **username_0**: Two small questions. What type of self-reducibility are we talking about here? Randomised self-reducibility? And second, any more specific ideas for question 2? Thanks in advance  
> **username_1**: Check out Sinclair and Jerrum's paper (http://www.cs.berkeley.edu/~sinclair/approx.pdf) for the definition of self-reducibility, informal (p.94) and formal (p.99). It's quite different from randomised self-reducibility. For question 2 - I believe the theorem I quoted is the "indirect" general result being referred to.  

---

