Abstract
We devise a framework for proving tight lower bounds under the counting exponential-time hypothesis \(\mathsf {\#ETH}\) introduced by Dell et al. Our framework allows to convert many known \(\mathsf {\#P}\)-hardness results for counting problems into results of the following type: If the given problem admits an algorithm with running time \(2^{o(n)}\) on graphs with \(n\) vertices and \(\mathcal {O}(n)\) edges, then \(\mathsf {\#ETH}\) fails. As exemplary applications of this framework, we obtain such tight lower bounds for the evaluation of the zero-one permanent, the matching polynomial, and the Tutte polynomial on all non-easy points except for two lines.
R. Curticapean—Supported by ERC Starting Grant PARAMTIGHT (No. 280152).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bläser, M., Dell, H.: Complexity of the Cover Polynomial. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 801–812. Springer, Heidelberg (2007)
Bulatov, A.A.: The Complexity of the Counting Constraint Satisfaction Problem. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 646–661. Springer, Heidelberg (2008)
Cai, J.-Y., Chen, X.: Complexity of counting CSP with complex weights. STOC 2012, 909–920 (2012)
Cai, J.-Y., Lu, P., Xia, M.: A Computational Proof of Complexity of Some Restricted Counting Problems. In: Chen, J., Cooper, S.B. (eds.) TAMC 2009. LNCS, vol. 5532, pp. 138–149. Springer, Heidelberg (2009)
Cai, J., Pinyan, L., Xia, M.: Dichotomy for Holant* problems of boolean domain. SODA 2011, 1714–1728 (2011)
Dagum, P., Luby, M.: Approximating the permanent of graphs with large factors. Theor. Comput. Sci. 102(2), 283–305 (1992)
Dell, H., Husfeldt, T., Marx, D., Taslaman, N., Wahlen, M.: Exponential time complexity of the permanent and the tutte polynomial. ACM Transactions on Algorithms 10(4), 21 (2014)
Leslie Ann Goldberg and Mark Jerrum: The complexity of computing the sign of the tutte polynomial. SIAM J. Comput. 43(6), 1921–1952 (2014)
Hoffmann, C.: Exponential Time Complexity of Weighted Counting of Independent Sets. In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol. 6478, pp. 180–191. Springer, Heidelberg (2010)
Husfeldt, T., Taslaman, N.: The Exponential Time Complexity of Computing the Probability That a Graph Is Connected. In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol. 6478, pp. 192–203. Springer, Heidelberg (2010)
Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Computer and Sys. Sci. 63(4), 512–530 (2001)
Jaeger, F., Vertigan, D.L., Welsh, D J.A.: On the computational complexity of the Jones and Tutte polynomials. Mathematical Proceedings of the Cambridge Philosophical Society 108(1), 35–53 (1990)
Jerrum, M., Sinclair, A., Vigoda, E.: A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM 51(4), 671–697 (2004)
Linial, N.: Hard enumeration problems in geometry and combinatorics. SIAM Journal on Algebraic and Discrete Methods 7(2), 331–335 (1986)
Sokal, A.D.: The multivariate Tutte polynomial (alias Potts model) for graphs and matroids. Surveys in Combinatorics 327, 173–226 (2005)
Vadhan, S.P.: The complexity of counting in sparse, regular, and planar graphs. SIAM J. Comput. 31(2), 398–427 (2001)
Valiant, L.G.: The complexity of computing the permanent. Theoretical Computer Science 8(2), 189–201 (1979)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Curticapean, R. (2015). Block Interpolation: A Framework for Tight Exponential-Time Counting Complexity. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9134. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47672-7_31
Download citation
DOI: https://doi.org/10.1007/978-3-662-47672-7_31
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47671-0
Online ISBN: 978-3-662-47672-7
eBook Packages: Computer ScienceComputer Science (R0)