 License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2018.7
URN: urn:nbn:de:0030-drops-99068
URL: https://drops.dagstuhl.de/opus/volltexte/2018/9906/
 Go to the corresponding LIPIcs Volume Portal

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

 pdf-format:

### 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 rank-r 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-hard, parameterized by k. The problem is MINI-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:1--7:18},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-093-4},
ISSN =	{1868-8969},
year =	{2018},
volume =	{122},
editor =	{Sumit Ganguly and Paritosh Pandya},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
DROPS-Home | Fulltext Search | Imprint | Privacy 