Ideal Membership Problem over 3-Element CSPs with Dual Discriminator Polymorphism

DOI10.1137/21M1397131zbMath1492.68061MaRDI QIDQ5096588

Arpitha P. Bharathi, Monaldo Mastrolilli

Publication date: 18 August 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

constraint satisfaction problemspolymorphismsGröbner basis theorypolynomial ideal membership

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Polynomial rings and ideals; rings of integer-valued polynomials (13F20) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Representing and solving finite-domain constraint problems using systems of polynomials
• Einstein and the Kaluza-Klein particle
• The membership problem for unmixed polynomial ideals is solvable in single exponential time
• From local to global consistency
• On the algebraic structure of combinatorial problems
• Constraint satisfaction problems: complexity and algorithms
• The complexity of the word problems for commutative semigroups and polynomial ideals
• 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 CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA
• Recent Results on Polynomial Identity Testing
• Theta Bodies for Polynomial Ideals
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• On the Shannon capacity of a graph
• Closure properties of constraints
• SOS Is Not Obviously Automatizable, Even Approximately
• Membership in polynomial ideals over Q is exponential space complete
• On the Bit Complexity of Sum-of-Squares Proofs
• The Complexity of the Ideal Membership Problem for Constrained Problems Over the Boolean Domain
• Ideals, Varieties, and Algorithms
• The complexity of satisfiability problems