*Abstract:*

We prove two results concerning approximate counting of
independent sets in graphs with constant maximum degree
*Delta*. The first implies that the Monte Carlo Markov chain
technique is likely to fail if *Delta* >= 6. The second
shows that no fully polynomial randomized approximation scheme can
exist if *Delta* >= 25, unless RP=NP.

This report is available in the following formats:

- PDF file
- Gzipped PDF file
- PostScript file
- Gzipped PostScript file
- PostScript file with Type 1 fonts
- Gzipped PostScript file with Type 1 fonts
- LaTeX DVI file
- Gzipped LaTeX DVI file