The fine-grained complexity of computing the tutte polynomial of a linear matroid
We show that computing the Tutte polynomial of a linear matroid of dimension k on kO(1) points over a field of kO(1) elements requires kΩ(k) time unless the #ETH-a counting extension of the Exponential Time Hypothesis of Impagliazzo and Paturi [CCC 1999] due to Dell et al. [ACM TALG 2014]-is false. This holds also for linear matroids that admit a representation where every point is associated to a
