On testing monomials in multivariate polynomials

DOI10.1016/j.tcs.2012.03.038zbMath1372.68292OpenAlexW2045732794MaRDI QIDQ391220

Robert T. Schweller, Bin Fu, Yang Liu, Zhixiang 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

complexityrandomizationmonomialsmultivariate polynomialsderandomizationalgebramonomial testing

Mathematics Subject Classification ID

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

Related Items

On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• PRIMES is in P
• Deterministic polynomial identity testing in non-commutative models
• Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials
• Proof verification and the hardness of approximation problems
• Primality and identity testing via Chinese remaindering
• Faster Algebraic Algorithms for Path and Packing Problems
• Algorithms for maximum independent sets
• SeparatingPH fromPP by relativization
• IP = PSPACE
• Interactive proofs and the hardness of approximating cliques
• Learning DNF in time
• The Complexity of Testing Monomials in Multivariate Polynomials
• 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