6
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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 [...]

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Paramar
    Feb 19, 2015 at 3:13
  • 1
    $\begingroup$ Check out Sinclair and Jerrum's paper (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. $\endgroup$ Feb 20, 2015 at 7:32

Your Answer

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

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