2026-08-18T03:19:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9906 2024-03-06T10:45:04Z ddc:004 open_access

Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators Arvind, V. Chatterjee, Abhranil Datta, Rajit Mukhopadhyay, Partha Combinatorial Nullstellensatz Ideal Membership Parametric Hardness Low Rank Permanent 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[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}>. Schloss Dagstuhl – Leibniz-Zentrum für Informatik V. Arvind and Abhranil Chatterjee and Rajit Datta and Partha Mukhopadhyay 2018 Is Part Of LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2018.7 urn:nbn:de:0030-drops-99068 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.7 eng https://creativecommons.org/licenses/by/3.0/legalcode