scientific article; zbMATH DE number 7559384

DOI10.4230/LIPICS.MFCS.2020.13MaRDI QIDQ5089174FDOQ5089174

Authors: Arpitha P. Bharathi, Monaldo Mastrolilli 

Publication date: 18 July 2022

Title of this publication is not available (Why is that?)

Recommendations

• The ideal membership problem and polynomial identity testing
• The complexity of the ideal membership problem for constrained problems over the Boolean domain
• The Complexity of the Ideal Membership Problem for Constrained Problems Over the Boolean Domain
• Ideal membership problem over 3-element CSPs with dual discriminator polymorphism
• scientific article; zbMATH DE number 7724189
• Complexity of membership problems of different types of polynomial ideals
• On the parallel complexity of the polynomial ideal membership problem
• The Complexity of the Membership Problem for Two Subclasses of Polynomial Ideals
• On the complexity of CSP-based ideal membership problems
• The Monomial Ideal Membership Problem and Polynomial Identity Testing

zbMATH Keywords

constraint satisfaction problemspolymorphismsGröbner basis theorypolynomial ideal membership

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Ideals, Varieties, and Algorithms
• On the Shannon capacity of a graph
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Sums of squares, moment matrices and optimization over polynomials
• Closure properties of constraints
• The complexity of satisfiability problems
• On the algebraic structure of combinatorial problems
• The constraint satisfaction problem and universal algebra
• Bruno Buchberger's PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. Translation from the German
• The complexity of the word problems for commutative semigroups and polynomial ideals
• Theta bodies for polynomial ideals
• Membership in polynomial ideals over \(\mathcal{Q}\) is exponential space complete
• Complexity of membership problems of different types of polynomial ideals
• Title not available (Why is that?)
• SOS is not obviously automatizable, even approximately
• On the bit complexity of sum-of-squares proofs
• The complexity of the ideal membership problem for constrained problems over the Boolean domain
• Recent results on polynomial identity testing

Cited In (2)

• Title not available (Why is that?)
• Ideal membership problem over 3-element CSPs with dual discriminator polymorphism

This page was built for publication:

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