Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

This paper is our third step towards developing a theory of testing monomials in multivariate polynomials and concentrates on two problems: (1) How to compute the coefficients of multilinear monomials; and (2) how to find a maximum multilinear monomial when the input is a ΠΣΠ polynomial. We first prove that the first problem is #P-hard and then devise a O ∗(3n s(n)) upper bound for this problem for any polynomial represented by an arithmetic circuit of size s(n). Later, this upper bound is improved to O ∗(2n) for ΠΣΠ polynomials. We then design fully polynomial-time randomized approximation schemes for this problem for ΠΣ polynomials. On the negative side, we prove that, even for ΠΣΠ polynomials with terms of degree ≤2, the first problem cannot be approximated at all for any approximation factor ≥1, nor “weakly approximated” in a much relaxed setting, unless P=NP. For the second problem, we first give a polynomial time λ-approximation algorithm for ΠΣΠ polynomials with terms of degrees no more a constant λ≥2. On the inapproximability side, we give a n (1−ϵ)/2 lower bound, for any ϵ>0, on the approximation factor for ΠΣΠ polynomials. When terms in these polynomials are constrained to degrees ≤2, we prove a 1.0476 lower bound, assuming P≠NP; and a higher 1.0604 lower bound, assuming the Unique Games Conjecture.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Agrawal M, Biswas S (2003) Primality and identity testing via Chinese remaindering. J ACM 50(4):429–443

    Article  MathSciNet  Google Scholar 

  • Agrawal M, Kayal N, Saxena N (2004) PRIMES is in P. Ann Math 160(2):781–793

    Article  MathSciNet  MATH  Google Scholar 

  • Arora S, Lund C, Motwani R, Sudan M, Szegedy M (1998) Proof verification and the hardness of approximation problems. J ACM 45(3):501–555

    Article  MathSciNet  MATH  Google Scholar 

  • Beigel R (1993) The polynomial method in circuit complexity. In: Proceedings of the eighth conference on structure in complexity theory, pp 82–95

    Chapter  Google Scholar 

  • Bshouty NH, Chen Z, Decatur SE, Homer S (1995) One the learnability of Z N -DNF formulas. In: Proceedings of the eighth annual conference on computational learning theory, COLT 1995, Santa Cruz, California, USA. ACM, New York, 1995, pp 198–205

    Chapter  Google Scholar 

  • Chen Z, Fu B (2010) Approximating multilinear monomial coefficients and maximum multilinear monomials in multilinear polynomials (extended abstract). In: Proceedings of the fourth international conference on combinatorial optimization and applications, COCOA 2010. Lecture notes in computer science, vol 6508, pp 309–323

    Chapter  Google Scholar 

  • Chen Z, Fu B (2011) The complexity of testing monomials in multivariate polynomials. In: Proceedings of the fourth international conference on combinatorial optimization and applications, COCOA 2011, August 2011. Lecture notes in computer science, vol 6831, pp 1–15

    Chapter  Google Scholar 

  • Chen Z-Z, Kao M-Y (2000) Reducing randomness via irrational numbers. SIAM J Comput 29(4):1247–1256

    Article  MathSciNet  MATH  Google Scholar 

  • Chen Z, Fu B, Zhu B (2006) The approximability of the exemplar breakpoint distance problem. In: Proceedings of the second annual international conference on algorithmic aspects in information and management (AAIM). Lecture notes in computer science, vol 4041. Springer, Berlin, pp 291–302

    Chapter  Google Scholar 

  • Chen J, Lu S, Sze S-H, Zhang F (2007) Improved algorithms for path, matching, and packing problems. In: SODA, pp 298–307

    Google Scholar 

  • Chen Z, Fowler RH, Fu B, Zhu B (2008) On the inapproximability of the exemplar conserved interval distance problem of genomes. J Comb Optim 15(2):201–221

    Article  MathSciNet  MATH  Google Scholar 

  • Chen Z, Fu B, Liu Y, Schweller R (2011) Algorithms for testing monomials in multivariate polynomials. In: Proceedings of the fifth international conference on combinatorial optimization and applications, COCOA 2011. Lecture notes in computer science, vol 6831, pp 16–30

    Chapter  Google Scholar 

  • Chen Z, Fu B, Liu Y, Schweller R (2012) On testing monomials in multivariate polynomials. Theor Comput Sci. doi:10.1016/j.tcs.2012.03.038

    Google Scholar 

  • Feige U, Goldwasser S, Lovász L, Safra S, Szegedy M (1996) Interactive proofs and the hardness of approximating cliques. J ACM 43(2):268–292

    Article  MathSciNet  MATH  Google Scholar 

  • Fu B (1992) Separating PH from PP by relativization. Acta Math Sin 8(3):329–336

    Article  MATH  Google Scholar 

  • Hästad J (2001) Some optimal inapproximability results. J ACM 48(4):798–859

    Article  MathSciNet  Google Scholar 

  • Jerrum M, Sinclaire A, Vigoda E (2004) A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J ACM 51(4):671–697

    Article  MathSciNet  MATH  Google Scholar 

  • Kabanets V, Impagliazzo R (2003) Derandomizing polynomial identity tests means proving circuit lower bounds. In: STOC, pp 355–364

    Google Scholar 

  • Khot S, Kindler G, Mossel E, O’Donnell R (2004) Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? In: Proceedings of the 45th annual IEEE symposium on foundations of computer science, FOCS’04, pp 146–154

    Chapter  Google Scholar 

  • Klivans A, Servedio RA (2001) Learning DNF in time \(2^{\tilde{O}(n^{1/3})}\). In: STOC, pp 258–265

    Google Scholar 

  • Koutis I (2008) Faster algebraic algorithms for path and packing problems. In: Proceedings of the international colloquium on automata, language and programming, ICALP. Lecture notes in computer science, vol 5125. Springer, Berlin, pp 575–586

    Chapter  Google Scholar 

  • Minsky M, Papert S (1968) Perceptrons. MIT Press, Cambridge (expanded edition 1988)

    Google Scholar 

  • Raz R, Shpilka A (2005) Deterministic polynomial identity testing in non-commutative models. Comput Complex 14(1):1–19

    Article  MathSciNet  MATH  Google Scholar 

  • Ryser HJ (1963) Combinatorial mathematics. Carus mathematical monographs, vol 14. Math. Assoc. of America, Washington

    MATH  Google Scholar 

  • Shamir A (1992) IP = PSPACE. J ACM 39(4):869–877

    Article  MathSciNet  MATH  Google Scholar 

  • Valiant LG (1979) The complexity of computing the permanent. Theor Comput Sci 8(2):189–201

    Article  MathSciNet  MATH  Google Scholar 

  • Williams R (2009) Finding paths of length k in O ∗(2k) time. Inf Process Lett 109:315–318

    Article  MATH  Google Scholar 

  • Zuckerman D (2007) Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput 3:103–128

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

An extended abstract of the present paper was reported in Chen and Fu (2010). Negative coefficients in polynomials are first considered in Chen et al. (2012) for monomial testing.

We thank Yang Liu and Robbie Schweller for many valuable discussions during our weekly seminar. We thank Yang Liu for presenting Koutis’ paper (2008) at the seminar. Bin Fu’s research is supported by an NSF CAREER Award, 2009 April 1 to 2014 March 31.

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Texas–Pan American, 1201 W. University Drive, Edinburg, TX, 78539, USA

    Zhixiang Chen & Bin Fu

Authors
  1. Zhixiang Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bin Fu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zhixiang Chen.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chen, Z., Fu, B. Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials. J Comb Optim 25, 234–254 (2013). https://doi.org/10.1007/s10878-012-9496-5

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-012-9496-5

Keywords

Search

Navigation