2022/09/24 by Bonnet, Édouard, Giocanti, Ugo, de Mendez, Patrice Ossona +1 · 1 citation
#68W01 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.2209.12023
We continue developing the theory around the twin-width of totally ordered binary structures, initiated in the previous paper of the series. We first introduce the notion of parity and linear minors of a matrix, which consists of iteratively replacing consecutive rows or consecutive columns with a linear combination of them. We show that a matrix class has bounded twin-width if and only if its linear-minor closure does not contain all matrices. We observe that the fixed-parameter tractable algorithm for first-order model checking on structures given with an O(1)-sequence (certificate of bounded twin-width) and the fact that first-order transductions of bounded twin-width classes have bounded twin-width, both established in Twin-width I, extend to first-order logic with modular counting quantifiers. We make explicit a win-win argument obtained as a by-product of Twin-width IV, and somewhat similar to bidimensionality, that we call rank-bidimensionality. Armed with the above-mentioned extension to modular counting, we show that the twin-width of the product of two conformal matrices A, B over a finite field is bounded by a function of the twin-width of A, of B, and of the size of the field. Furthermore, if A and B are n × n matrices of twin-width d over \mathbb Fq, we show that AB can be computed in time Od,q(n2 log n). We finally present an ad hoc algorithm to efficiently multiply two matrices of bounded twin-width, with a single-exponential dependence in the twin-width bound: If the inputs are given in a compact tree-like form, called twin-decomposition (of width d), then two n × n matrices A, B over \mathbb F2, a twin-decomposition of AB with width 2d+o(d) can be computed in time 4d+o(d)n (resp. 4d+o(d)n1+ε), and entries queried in doubly-logarithmic (resp. constant) time.