Univariate ideal membership parameterized by rank, degree, and number of generators

DOI10.4230/LIPICS.FSTTCS.2018.7MaRDI QIDQ5090939zbMATH OpenFDO

Authors Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay

Publication date 21 July 2022

zbMATH Keywords

combinatorial nullstellensatzideal membershiplow rank permanentparametric hardness

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Recommendations

• Univariate ideal membership parameterized by rank, degree, and number of generators
• The ideal membership problem and polynomial identity testing
• The Monomial Ideal Membership Problem and Polynomial Identity Testing
• The membership problem for unmixed polynomial ideals is solvable in single exponential time
• scientific article; zbMATH DE number 124343

Cites work

• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• A note on the permanent value problem
• A probabilistic remark on algebraic program testing
• An inequality for the discriminant of a polynomial
• Combinatorial Nullstellensatz
• Constrained multilinear detection and generalized graph motifs
• Constrained multilinear detection for faster functional motif discovery
• Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems
• Extensor-coding
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Faster Algebraic Algorithms for Path and Packing Problems
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• From sylvester-gallai configurations to rank bounds
• Hilbert's Nullstellensatz is in the polynomial hierarchy
• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• LIMITS and applications of group algebras for parameterized problems
• Parameterized algorithms
• Polynomial identity testing for depth 3 circuits
• Power sum decompositions of elementary symmetric polynomials
• Rank and chromatic number of a graph
• Subresultants and Reduced Polynomial Remainder Sequences
• The complexity of satisfiability problems
• The complexity of the word problems for commutative semigroups and polynomial ideals
• The ideal membership problem and polynomial identity testing
• The rank and size of graphs
• Two Algorithmic Results for the Traveling Salesman Problem

Cited in

(2)

• Patching colors with tensors
• Univariate ideal membership parameterized by rank, degree, and number of generators

This page was built for publication: Univariate ideal membership parameterized by rank, degree, and number of generators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090939)