On the parameterized complexity of approximate counting

J. Andrés Montoya

RAIRO - Theoretical Informatics and Applications (2011)

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

Abstract

top
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.

How to cite

top

André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
  1. M. Agrawal, N. Saxena and N. Kayal, PRIMES is in P . Annals of Math.160 (2004) 781–793.  Zbl1071.11070
  2. 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
  3. R.G. Downey and M.R. Fellows, Parameterized Complexity. Springer-Verlag (1999).  
  4. J. Flum and M. Grohe, The parameterized complexity of counting problems. SIAM J. Comput.33 (2004) 892–922.  Zbl1105.68042
  5. J. Flum and M. Grohe, Parameterized Complexity Theory. Springer-Verlag (2006).  Zbl1143.68016
  6. O. Goldreich, Randomized methods in Computation. Manuscript (2001) oded/rnd.html.  URIhttp://www.wisdom.weizmann.ac.il/
  7. C. Lautemann, B P P and the Polynomial Hierarchy. Inform. Process. Lett.17 (1983) 215–217.  
  8. J.A. Montoya, On parameterized Counting. Ph.D thesis, Freiburg University (2008).  Zbl1155.03023
  9. J.A. Montoya, The parameterized complexity of probability amplification. Inform. Process. Lett.109 (2008) 46–53.  Zbl1191.68342
  10. 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
  11. C.H. Papadimitriou, Computational Complexity. Addison-Wesley (1994).  
  12. L. Stockmeyer, On approximation Algorithms for # P . SIAM J. Comput.14 (1985) 849–861.  
  13. S. Toda, P P is as hard as the polynomial-time hierarchy. SIAM J. Comput.20 (1991) 865–877.  Zbl0733.68034
  14. L.G. Valiant, The complexity of computing the permanent. Theoret. Comput. Sci.8 (1979) 189–201.  Zbl0415.68008
  15. L.G. Valiant, The complexity of enumeration and reliability problems. SIAM J. Comput.8 (1979) 410–421.  Zbl0419.68082

NotesEmbed ?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.