Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators

• Published in: Theory of computing systems 2022-02, Vol.66 (1), p.56-88
• Main Authors: Arvind, V., Chatterjee, Abhranil, Datta, Rajit, Mukhopadhyay, Partha
• Format: Article
• Language: English
• Subjects: Algorithms; Circuits; Combinatorial analysis; Computer Science; Mathematical analysis; Parameters; Polynomials; Rings (mathematics); Theory of Computation
• ISSN: 1432-4350; 1433-0490
• DOI: 10.1007/s00224-021-10053-w

Let F [ X ] be the polynomial ring in the variables X = { x 1 , x 2 ,…, x n } over a field F . An ideal I = 〈 p 1 ( x 1 ),…, p n ( x n )〉 generated by univariate polynomials { p i ( x i ) } i = 1 n is a univariate ideal . Motivated by Alon’s Combinatorial Nullstellensatz we study the complexity of univariate ideal membership : Given f ∈ F [ X ] by a circuit and polynomials p i the problem is test if f ∈ I . We obtain the following results. Suppose f is a degree- d , rank- r polynomial given by an arithmetic circuit where ℓ i : 1 ≤ i ≤ r are linear forms in X . We give a deterministic time d O ( r ) ⋅poly( n ) division algorithm for evaluating the (unique) remainder polynomial f ( X )mod I at any point a → ∈ F n . This yields a randomized n O ( r ) algorithm for minimum vertex cover in graphs with rank- r adjacency matrices. It also yields a new n O ( r ) algorithm for evaluating the permanent of a n × n matrix of rank r , over any field F . Let f be over rationals with deg ( f ) = k treated as fixed parameter. When the ideal I = x 1 e 1 , … , x n e n , we can test ideal membership in randomized O ∗ ((2 e ) k ). On the other hand, if each p i has all distinct rational roots we can check if f ∈ I in randomized O ∗ ( n k /2 ) time, improving on the brute-force n + k k -time search. If I = p 1 ( x 1 ) , … , p k ( x k ) , with k as fixed parameter, then ideal membership testing is W[2]-hard. The problem is MINI[1]-hard in the special case when I = x 1 e 1 , … , x k e k .