Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials
DOI10.1007/s10878-012-9496-5zbMath1288.90072arXiv1007.2678OpenAlexW2786501561MaRDI QIDQ1944393
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
multivariate polynomialsapproximation algorithmsinapproximabilitymonomial testingmaximum multilinear monomialsmonomial coefficient computingmonomial coefficients
Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (5)
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