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

DOI10.4230/LIPICS.FSTTCS.2018.7MaRDI QIDQ5090939FDOQ5090939

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

Publication date: 21 July 2022

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

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)

Cites Work

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