Determinantal Sieving

We introduce a new, remarkably powerful tool to the toolbox of algebraic FPT algorithms, determinantal sieving. Given evaluation access to a polynomial 𝑃(𝑥 1 , . . . , 𝑥 𝑛 ) over a field F of characteristic 2, defined on the set of variables 𝑋 = 𝑥 1 , . . . , 𝑥 𝑛 , and a linear matroid 𝑀 = (𝑋, I) over F of rank 𝑘, one can determine -with 𝑂 * (2 𝑘 ) evaluations of 𝑃 (where 𝑂 * suppresses factors polynomial in the input size) -whether there exists a multilinear term in the monomial expansion of 𝑃 whose support forms a basis for 𝑀. The known tools of multilinear detection and constrained multilinear detection then correspond to the case where 𝑀 is a uniform matroid and the truncation of a disjoint union of uniform matroids, respectively. More generally, let the odd support of a monomial 𝑚 be the set of variables which have odd degree in 𝑚. Using 𝑂 * (2 𝑘 ) evaluations of 𝑃, we can sieve for those terms 𝑚 whose odd support spans 𝑀. Applying this framework to well-known efficiently computable polynomial families allows us to simplify, generalize and improve on a range of algebraic FPT algorithms, such as: Solving 𝑞-Matroid Intersection in time 𝑂 * (2 (𝑞-2)𝑘 ) and 𝑞-Matroid Parity in time 𝑂 * (2 𝑞𝑘 ), improving on 𝑂 * (4 𝑞𝑘 ) for matroids represented over general fields (Brand and Pratt, ICALP 2021) Long (𝑠, 𝑡)-Path in 𝑂 * (1.66 𝑘 ) time, improving on 𝑂 * (2 𝑘 ) (Fomin et al., SODA 2023), as well as further results on paths and linkages in so-called frameworks, including Rank 𝑘 (𝑆, 𝑇 )-Linkage in 𝑂 * (2 𝑘 ) time (improving on 𝑂 * (2 |𝑆|+𝑂(𝑘 2 log(𝑘+|F|)) ) over general fields by Fomin et al.) Many instances of the Diverse X paradigm, finding a collection of 𝑟 solutions to a problem with a minimum mutual distance of 𝑑 in time 𝑂 * (2 𝑟 2 𝑑/2 ), improving solutions for 𝑘-Distinct A preliminary version of this work was presented at SODA 2024 [47].