On testing monomials in multivariate polynomials

DOI10.1016/J.TCS.2012.03.038MaRDI QIDQ391220zbMATH OpenOpenAlexFDO

Authors Bin Fu, Yang Liu, Robert T. Schweller, Zhi-Xiang Chen

Publication date 10 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.03.038

zbMATH Keywords

randomizationcomplexityalgebraderandomizationmonomialsmultivariate polynomialsmonomial testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• The complexity of testing monomials in multivariate polynomials
• Algorithms for testing monomials in multivariate polynomials
• Monomial testing and applications
• Toward randomized testing of \(q\)-monomials in multivariate polynomials

Cites work

• scientific article; zbMATH DE number 46318 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 1418967 (Why is no real title available?)
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Algorithms for maximum independent sets
• Algorithms for testing monomials in multivariate polynomials
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Deterministic polynomial identity testing in non-commutative models
• Faster Algebraic Algorithms for Path and Packing Problems
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• IP = PSPACE
• Improved algorithms for path, matching, and packing problems
• Interactive proofs and the hardness of approximating cliques
• Learning DNF in time
• PRIMES is in P
• Primality and identity testing via Chinese remaindering
• Proof verification and the hardness of approximation problems
• SeparatingPH fromPP by relativization
• The complexity of computing the permanent
• The complexity of testing monomials in multivariate polynomials

Cited in

(9)

• Algorithms for testing monomials in multivariate polynomials
• The complexity of testing monomials in multivariate polynomials
• scientific article; zbMATH DE number 2219805 (Why is no real title available?)
• Detecting monomials with \(k\) distinct variables
• scientific article; zbMATH DE number 5232260 (Why is no real title available?)
• Toward randomized testing of \(q\)-monomials in multivariate polynomials
• The Monomial Ideal Membership Problem and Polynomial Identity Testing
• On proving parameterized size lower bounds for multilinear algebraic models
• Monomial testing and applications

This page was built for publication: On testing monomials in multivariate polynomials

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