Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials

DOI10.1007/s10878-012-9496-5zbMath1288.90072arXiv1007.2678OpenAlexW2786501561MaRDI QIDQ1944393

Zhixiang Chen, Bin Fu

Publication date: 25 March 2013

Published in: Journal of Combinatorial Optimization, Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1007.2678

zbMATH Keywords

multivariate polynomialsapproximation algorithmsinapproximabilitymonomial testingmaximum multilinear monomialsmonomial coefficient computingmonomial coefficients

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (5)

On testing monomials in multivariate polynomials ⋮ Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials ⋮ On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models ⋮ Monomials in arithmetic circuits: complete problems in the counting hierarchy ⋮ TOWARD RANDOMIZED TESTING OF q-MONOMIALS IN MULTIVARIATE POLYNOMIALS

Cites Work

• NP-completeness and APX-completeness of restrained domination in graphs
• The complexity of computing the permanent
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• PRIMES is in P
• Deterministic polynomial identity testing in non-commutative models
• Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials
• On the inapproximability of the exemplar conserved interval distance problem of genomes
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Proof verification and the hardness of approximation problems
• Primality and identity testing via Chinese remaindering
• Faster Algebraic Algorithms for Path and Packing Problems
• SeparatingPH fromPP by relativization
• IP = PSPACE
• Interactive proofs and the hardness of approximating cliques
• Reducing Randomness via Irrational Numbers
• Learning DNF in time
• The Complexity of Testing Monomials in Multivariate Polynomials
• Algorithms for Testing Monomials in Multivariate Polynomials
• The Approximability of the Exemplar Breakpoint Distance Problem
• Some optimal inapproximability results
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials