The finegrained complexity of computing the tutte polynomial of a linear matroid
(2021) 32nd Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2021 In Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms p.23332345 Abstract
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^{Ω(}k) time unless the #ETHa 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 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... (More)
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^{Ω(}k) time unless the #ETHa 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 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 kvertex graph (that is, the Tutte polynomial of a graphic matroid of dimension kwhich 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örklund et al., FOCS 2008]. Our lowerbound proofs proceed in three steps: 1. 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; 2. an earlierestablished #ETHhardness of counting the solutions to a bipartite (d, 2)CSP on n vertices in d^{o}(n) time; and 3. new embeddings of such CSP instances as questions about codewords of full support in a linear code. Geometrically, our hardness results also establish that it is #ETHhard to compute the volume of proper hyperplane chambers in time k^{o}(k) for a given arrangement of hyperplanes through the origin of a finite kdimensional vector space over a k^{O}^{(1)}element field. We complement these lower bounds with two algorithm designs to form essentially a complexity dichotomy under #ETH. The first design computes the Tutte polynomial of a linear matroid of dimension k on k^{O}^{(1)} points in k^{O}(k) arithmetic operations in the base field. The second design generalizes the Björklund et al. algorithm from the graphic case and runs in q^{k}^{+1}k^{O}^{(1)} time for linear matroids of dimension k defined over the qelement field by k^{O}^{(1)} points with at most two nonzero coordinates each.
(Less)
 author
 Björklund, Andreas ^{LU} and Kaski, Petteri
 organization
 publishing date
 2021
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 host publication
 ACMSIAM Symposium on Discrete Algorithms, SODA 2021
 series title
 Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
 editor
 Marx, Daniel
 pages
 13 pages
 publisher
 Association for Computing Machinery (ACM)
 conference name
 32nd Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2021
 conference location
 Alexandria, Virtual, United States
 conference dates
 20210110  20210113
 external identifiers

 scopus:85097815594
 ISBN
 9781611976465
 language
 English
 LU publication?
 yes
 id
 947c110307d34cb984d6f94f6acd8d23
 date added to LUP
 20220103 12:52:33
 date last changed
 20220427 07:00:48
@inproceedings{947c110307d34cb984d6f94f6acd8d23, abstract = {{<p>We show that computing the Tutte polynomial of a linear matroid of dimension k on k<sup>O</sup><sup>(1)</sup> points over a field of k<sup>O</sup><sup>(1)</sup> elements requires k<sup>Ω(</sup>k) time unless the #ETHa 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 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<sup>O</sup><sup>(1)</sup> 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 kvertex graph (that is, the Tutte polynomial of a graphic matroid of dimension kwhich 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<sup>k</sup>k<sup>O</sup><sup>(1)</sup> time [Björklund et al., FOCS 2008]. Our lowerbound proofs proceed in three steps: 1. 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; 2. an earlierestablished #ETHhardness of counting the solutions to a bipartite (d, 2)CSP on n vertices in d<sup>o</sup>(n) time; and 3. new embeddings of such CSP instances as questions about codewords of full support in a linear code. Geometrically, our hardness results also establish that it is #ETHhard to compute the volume of proper hyperplane chambers in time k<sup>o</sup>(k) for a given arrangement of hyperplanes through the origin of a finite kdimensional vector space over a k<sup>O</sup><sup>(1)</sup>element field. We complement these lower bounds with two algorithm designs to form essentially a complexity dichotomy under #ETH. The first design computes the Tutte polynomial of a linear matroid of dimension k on k<sup>O</sup><sup>(1)</sup> points in k<sup>O</sup>(k) arithmetic operations in the base field. The second design generalizes the Björklund et al. algorithm from the graphic case and runs in q<sup>k</sup><sup>+1</sup>k<sup>O</sup><sup>(1)</sup> time for linear matroids of dimension k defined over the qelement field by k<sup>O</sup><sup>(1)</sup> points with at most two nonzero coordinates each.</p>}}, author = {{Björklund, Andreas and Kaski, Petteri}}, booktitle = {{ACMSIAM Symposium on Discrete Algorithms, SODA 2021}}, editor = {{Marx, Daniel}}, isbn = {{9781611976465}}, language = {{eng}}, pages = {{23332345}}, publisher = {{Association for Computing Machinery (ACM)}}, series = {{Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms}}, title = {{The finegrained complexity of computing the tutte polynomial of a linear matroid}}, year = {{2021}}, }