Block Interpolation: A Framework for Tight Exponential-Time Counting Complexity

The complexity of computing the permanent

Leslie G. Valiant · 1979

Earlier work this paper cites.

The Tutte polynomial, matroid theory and its applications

Thomas Brylawski · 1982

Earlier work this paper cites.

Hard enumeration problems in geometry and combinatorics

Nathan Linial · 1986

Earlier work this paper cites.

Relations among Mod-classes

Ulrich Hertrampf · 1990

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.

Approximating the permanent of graphs with large factors

Paul Dagum and Michael Luby · 1992

Earlier work this paper cites.

On the complexity of k k -SAT

Russel Impagliazzo and Ramamohan Paturi · 2001

Earlier work this paper cites.

Which problems have strongly exponential complexity?

Russell Impagliazzo, Ramamohan Paturi, and Francis Zane · 2001

Earlier work this paper cites.

The complexity of counting in sparse, regular, and planar graphs

Salil P. Vadhan · 2001

Earlier work this paper cites.

A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries

Mark Jerrum, Alistair Sinclair, and Eric Vigoda · 2004

Earlier work this paper cites.

Matrix Analysis For Scientists And Engineers

Alan J. Laub · 2004

Cited alongside, same era.

The independence polynomial of a graph - a survey

Vadim E. Levit and Eugen Mandrescu · 2005

Cited alongside, same era.

The multivariate Tutte polynomial (alias Potts model) for graphs and matroids

Alan D. Sokal · 2005

Cited alongside, same era.

Accidental algorithms

Leslie G. Valiant · 2006

Cited alongside, same era.

Complexity of the cover polynomial

Markus Bläser and Holger Dell · 2007

Cited alongside, same era.

The complexity of the counting constraint satisfaction problem

Andrei A. Bulatov · 2008

Cited alongside, same era.

Inapproximability of the Tutte polynomial

The complexity of the cover polynomials for planar graphs of bounded degree

Markus Bläser and Radu Curticapean · 2011

Later among the works it cites.

Dichotomy for Holant* problems of boolean domain

Jin-yi Cai, Pinyan Lu, and Mingji Xia · 2011

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.

The exponential time hypothesis and the parameterized clique problem

Yijia Chen, Kord Eickmeyer, and Jörg Flum · 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 Wahlen · 2014

Later among the works it cites.

The complexity of computing the sign of the Tutte polynomial

Leslie Ann Goldberg and Mark Jerrum · 2014

Later among the works it cites.