# On the parameterized complexity of approximate counting

RAIRO - Theoretical Informatics and Applications (2011)

- Volume: 45, Issue: 2, page 197-223
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topAndrés Montoya, J.. "On the parameterized complexity of approximate counting." RAIRO - Theoretical Informatics and Applications 45.2 (2011): 197-223. <http://eudml.org/doc/276338>.

@article{AndrésMontoya2011,

abstract = {
In this paper we study the parameterized complexity of approximating the
parameterized counting problems contained in the class $\#W[P]$,
the parameterized analogue of $\#P$. We prove a parameterized analogue of a
famous theorem of Stockmeyer claiming that approximate counting belongs to
the second level of the polynomial hierarchy.
},

author = {Andrés Montoya, J.},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Computational complexity; parameterized complexity; counting
problems; approximate counting; computational complexity; counting problems},

language = {eng},

month = {6},

number = {2},

pages = {197-223},

publisher = {EDP Sciences},

title = {On the parameterized complexity of approximate counting},

url = {http://eudml.org/doc/276338},

volume = {45},

year = {2011},

}

TY - JOUR

AU - Andrés Montoya, J.

TI - On the parameterized complexity of approximate counting

JO - RAIRO - Theoretical Informatics and Applications

DA - 2011/6//

PB - EDP Sciences

VL - 45

IS - 2

SP - 197

EP - 223

AB -
In this paper we study the parameterized complexity of approximating the
parameterized counting problems contained in the class $\#W[P]$,
the parameterized analogue of $\#P$. We prove a parameterized analogue of a
famous theorem of Stockmeyer claiming that approximate counting belongs to
the second level of the polynomial hierarchy.

LA - eng

KW - Computational complexity; parameterized complexity; counting
problems; approximate counting; computational complexity; counting problems

UR - http://eudml.org/doc/276338

ER -

## References

top- M. Agrawal, N. Saxena and N. Kayal, PRIMES is in $P.$Annals of Math.160 (2004) 781–793. Zbl1071.11070
- V. Arvind and V. Raman, Approximation algorithms for some parameterized counting problems, in Proceedings of the 13th Annual International Symposium on Algorithms and Computation, edited by P. Bose and P. Morin. Lect. Notes Comput. Sci.2518 (2002) 453–464. Zbl1019.68135
- R.G. Downey and M.R. Fellows, Parameterized Complexity. Springer-Verlag (1999).
- J. Flum and M. Grohe, The parameterized complexity of counting problems. SIAM J. Comput.33 (2004) 892–922. Zbl1105.68042
- J. Flum and M. Grohe, Parameterized Complexity Theory. Springer-Verlag (2006). Zbl1143.68016
- O. Goldreich, Randomized methods in Computation. Manuscript (2001) oded/rnd.html. URIhttp://www.wisdom.weizmann.ac.il/
- C. Lautemann, $BPP$ and the Polynomial Hierarchy. Inform. Process. Lett.17 (1983) 215–217.
- J.A. Montoya, On parameterized Counting. Ph.D thesis, Freiburg University (2008). Zbl1155.03023
- J.A. Montoya, The parameterized complexity of probability amplification. Inform. Process. Lett.109 (2008) 46–53. Zbl1191.68342
- M. Muller, Randomized approximations of parameterized counting problems. Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC'06). Lect. Notes Comput. Sci. 4169 (2006) 50–59. Zbl1154.68433
- C.H. Papadimitriou, Computational Complexity. Addison-Wesley (1994).
- L. Stockmeyer, On approximation Algorithms for $\#P.$SIAM J. Comput.14 (1985) 849–861.
- S. Toda, $PP$ is as hard as the polynomial-time hierarchy. SIAM J. Comput.20 (1991) 865–877. Zbl0733.68034
- L.G. Valiant, The complexity of computing the permanent. Theoret. Comput. Sci.8 (1979) 189–201. Zbl0415.68008
- L.G. Valiant, The complexity of enumeration and reliability problems. SIAM J. Comput.8 (1979) 410–421. Zbl0419.68082

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.