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
topHow 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 Annals of Math.160 (2004) 781–793.
- 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.
- 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.
- J. Flum and M. Grohe, Parameterized Complexity Theory. Springer-Verlag (2006).
- O. Goldreich, Randomized methods in Computation. Manuscript (2001) oded/rnd.html. URIhttp://www.wisdom.weizmann.ac.il/
- C. Lautemann, and the Polynomial Hierarchy. Inform. Process. Lett.17 (1983) 215–217.
- J.A. Montoya, On parameterized Counting. Ph.D thesis, Freiburg University (2008).
- J.A. Montoya, The parameterized complexity of probability amplification. Inform. Process. Lett.109 (2008) 46–53.
- 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.
- C.H. Papadimitriou, Computational Complexity. Addison-Wesley (1994).
- L. Stockmeyer, On approximation Algorithms for SIAM J. Comput.14 (1985) 849–861.
- S. Toda, is as hard as the polynomial-time hierarchy. SIAM J. Comput.20 (1991) 865–877.
- L.G. Valiant, The complexity of computing the permanent. Theoret. Comput. Sci.8 (1979) 189–201.
- L.G. Valiant, The complexity of enumeration and reliability problems. SIAM J. Comput.8 (1979) 410–421.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.