Abstract
Let F[X] be the polynomial ring over the variables X={x_1,x_2, ..., x_n}. 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. We study the ideal membership problem for the univariate ideals and show the following results.
 Let f(X) in F[l_1, ..., l_r] be a (low rank) polynomial given by an arithmetic circuit where l_i : 1 <= i <= r are linear forms, and I=<p_1(x_1), ..., p_n(x_n)> be a univariate ideal. Given alpha in F^n, the (unique) remainder f(X) mod I can be evaluated at alpha in deterministic time d^{O(r)} * poly(n), where d=max {deg(f),deg(p_1)...,deg(p_n)}. This yields a randomized n^{O(r)} algorithm for minimum vertex cover in graphs with rankr adjacency matrices. It also yields an n^{O(r)} algorithm for evaluating the permanent of a n x n matrix of rank r, over any field F. Over Q, an algorithm of similar run time for low rank permanent is due to Barvinok [Barvinok, 1996] via a different technique.
 Let f(X)in F[X] be given by an arithmetic circuit of degree k (k treated as fixed parameter) and I=<p_1(x_1), ..., p_n(x_n)>. We show that in the special case when I=<x_1^{e_1}, ..., x_n^{e_n}>, we obtain a randomized O^*(4.08^k) algorithm that uses poly(n,k) space.
 Given f(X)in F[X] by an arithmetic circuit and I=<p_1(x_1), ..., p_k(x_k)>, membership testing is W[1]hard, parameterized by k. The problem is MINI[1]hard in the special case when I=<x_1^{e_1}, ..., x_k^{e_k}>.
BibTeX  Entry
@InProceedings{arvind_et_al:LIPIcs:2018:9906,
author = {V. Arvind and Abhranil Chatterjee and Rajit Datta and Partha Mukhopadhyay},
title = {{Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators}},
booktitle = {38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
pages = {7:17:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770934},
ISSN = {18688969},
year = {2018},
volume = {122},
editor = {Sumit Ganguly and Paritosh Pandya},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9906},
URN = {urn:nbn:de:0030drops99068},
doi = {10.4230/LIPIcs.FSTTCS.2018.7},
annote = {Keywords: Combinatorial Nullstellensatz, Ideal Membership, Parametric Hardness, Low Rank Permanent}
}
Keywords: 

Combinatorial Nullstellensatz, Ideal Membership, Parametric Hardness, Low Rank Permanent 
Collection: 

38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018) 
Issue Date: 

2018 
Date of publication: 

05.12.2018 