We show that computing the Tutte polynomial of a linear matroid of dimension k on k^{O(1)} points over a field of k^{O(1)} elements requires k^{\Omega(k)} time unless the  ETH---a counting extension of the Exponential Time Hypothesis of Impagliazzo and Paturi [CCC 1999] due to Dell {\em et al. [ACM TALG 2014]---is false. This holds also for linear matroids that admit a representation where every point is associated to a vector with at most two nonzero coordinates. Moreover, we also show that the same is true for computing the Tutte polynomial of a binary matroid of dimension k on k^{O(1)} points with at most three nonzero coordinates in each point's vector. These two results stand in sharp contrast to computing the Tutte polynomial of a k-vertex graph (that is, the Tutte polynomial of a graphic {\em  matroid of dimension k---which is representable in dimension k over the binary field so that every vector has exactly two nonzero coordinates), which is known to be computable in 2^k k^{O(1)} time [Bj\"orklund {\em et al. , FOCS 2008]. Our lower-bound proofs proceed in three steps: (i) a classic connection due to Crapo and Rota [1970] between the number of tuples of codewords of full support and the Tutte polynomial of the matroid associated with the code; (ii) an earlier-established \#ETH-hardness of counting the solutions to a bipartite (d,2)-CSP on n vertices in d^{o(n)} time; and (iii) new embeddings of such CSP instances as questions about codewords of full support in a linear code. We complement these lower bounds with a matching upper-bound algorithm design that computes the Tutte polynomial of a linear matroid of dimension  k on k^{O(1)} points in k^{O(k)} arithmetic operationsin the base field{\em   .
We show that computing the Tutte polynomial of a linear matroid of dimension k on k^{O(1)} points over a field of k^{O(1)} elements requires k^{\Omega(k)} time unless the \# ETH---a counting extension of the Exponential Time Hypothesis of Impagliazzo and Paturi [CCC 1999] due to Dell {\em et al. [ACM TALG 2014]---is false. This holds also for linear matroids that admit a representation where every point is associated to a vector with at most two nonzero coordinates. We also show that the same is true for computing the Tutte polynomial of a binary matroid of dimension k on k^{O(1)} points with at most three nonzero coordinates in each point's vector. This is in sharp contrast to computing the Tutte polynomial of a k-vertex graph (that is, the Tutte polynomial of a {\em graphic matroid of dimension k---which is representable in dimension k over the binary field so that every vector has two nonzero coordinates), which is known to be computable in 2^k k^{O(1)} time [Bj\"orklund {\em et al. , FOCS 2008]. Our lower-bound proofs proceed via (i) a connection due to Crapo and Rota [1970] between the number of tuples of codewords of full support and the Tutte polynomial of the matroid associated with the code; (ii) an earlier-established \#ETH-hardness of counting the solutions to a bipartite (d,2)-CSP on n vertices in d^{o(n)} time; and (iii) new embeddings of such CSP instances as questions about codewords of full support in a linear code. We complement these lower bounds with two algorithm designs. The first design computes the Tutte polynomial of a linear matroid of dimension ~ k on k^{O(1)} points in k^{O(k)} operations. The second design generalizes the Bj\"orklund~{\em et al. algorithm and runs in q^{k+1 .
A
\#
R
Moreover, we
We
R
These two results stand
This is
D
graphic
A
graphic
D
exactly
R
in three steps:
via
D
classic
R
a matching upper-bound algorithm design that
two algorithm designs. The first design
A
~
R
arithmetic operationsin the base field
operations. The second design generalizes the Bj\"orklund~
A
et al.
A
algorithm and runs in q^{k+1