Fetching the paper…
Reading the bibliography…
Jaeger, Vertigan, and Welsh [15] proved a dichotomy for the complexity of evaluating the Tutte polynomial at fixed points: The evaluation is #P-hard almost everywhere, and the remaining points admit polynomial-time algorithms.
The complexity of computing the permanent
Leslie G. Valiant · 1979
Earlier work this paper cites.
The complexity of counting cuts and of computing the probability that a graph is connected
J. Scott Provan and Michael O Ball · 1983
Earlier work this paper cites.
On the computational complexity of the Jones and Tutte polynomials
François Jaeger, Dirk L. Vertigan, and Dominic J.A. Welsh · 1990
Earlier work this paper cites.
PP is as hard as the polynomial-time hierarchy
Seinosuke Toda · 1991
Earlier work this paper cites.
On the computational complexity of Tutte, Jones, Homfly and Kauffman invariants
Dirk Llewellyn Vertigan · 1991
Earlier work this paper cites.
Complexity of generalized satisfiability counting problems
Nadia Creignou and Miki Hermann · 1996
Earlier work this paper cites.
On the complexity of k k -SAT
Russell Impagliazzo and Ramamohan Paturi · 2000
Earlier work this paper cites.
Which problems have strongly exponential complexity?
Russell Impagliazzo, Ramamohan Paturi, and Francis Zane · 2001
Cited alongside, same era.
The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
Alan D. Sokal · 2005
Cited alongside, same era.
A duality between clause width and clause density for sat
Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi · 2006
Cited alongside, same era.
Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh
Geoffrey Grimmett and Colin McDiarmid, editors · 2007
Cited alongside, same era.
Computing the Tutte polynomial in vertex-exponential time
Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto · 2008
Cited alongside, same era.
Exponential time complexity of the permanent and the Tutte polynomial
Holger Dell, Thore Husfeldt, and Martin Wahlén · 2010
The exponential time complexity of computing the probability that a graph is connected
Thore Husfeldt and Nina Taslaman · 2010
Later among the works it cites.
Computational complexity of holant problems
Jin-Yi Cai, Pinyan Lu, and Mingji Xia · 2011
Later among the works it cites.
Counting perfect matchings as fast as ryser
Andreas Björklund · 2012
Later among the works it cites.
Complexity of counting CSP with complex weights
Jin-Yi Cai and Xi Chen · 2012
Later among the works it cites.
Exponential time complexity of the permanent and the Tutte polynomial
Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlén · 2014
Later among the works it cites.
Block interpolation: A framework for tight exponential-time counting complexity
Radu Curticapean · 2015
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
CRC handbook on the Tutte polynomial and related topics
Joanna Ellis-Monaghan and Iain Moffatt
Cited in the paper.