Document Open Access Logo

On Some Computations on Sparse Polynomials

Author Ilya Volkovich

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.48.pdf
  • Filesize: 0.55 MB
  • 21 pages

Document Identifiers

Author Details

Ilya Volkovich

Cite As Get BibTex

Ilya Volkovich. On Some Computations on Sparse Polynomials. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 48:1-48:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.48

Abstract

In arithmetic circuit complexity the standard operations are +,x. Yet, in some scenarios exponentiation gates are considered as well. In this paper we study the question of efficiently evaluating a polynomial given an oracle access to its power. Among applications, we show that:

* A reconstruction algorithm for a circuit class c can be extended to handle f^e for f in C. 

* There exists an efficient deterministic algorithm for factoring sparse multiquadratic polynomials. 

* There is a deterministic algorithm for testing a factorization of sparse polynomials, with constant individual degrees, into sparse irreducible factors. That is, testing if f = g_1 x ... x g_m when f has constant individual degrees and g_i-s are irreducible.

* There is a deterministic reconstruction algorithm for multilinear depth-4 circuits with two multiplication gates. 

* There exists an efficient deterministic algorithm for testing whether two powers of sparse polynomials are equal. That is, f^d = g^e when f and g are sparse.

Subject Classification

Keywords
  • Derandomization
  • Arithmetic Circuits
  • Reconstruction

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. M. Agrawal, C. Saha, R. Saptharishi, and N. Saxena. Jacobian hits circuits: Hitting-sets, lower bounds for depth-d occur-k formulas & depth-3 transcendence degree-k circuits. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), pages 599-614, 2012. Google Scholar
  2. M. Agrawal and V. Vinay. Arithmetic circuits: A chasm at depth four. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 67-75, 2008. Google Scholar
  3. D. Angluin, L. Hellerstein, and M. Karpinski. Learning read-once formulas with queries. J. ACM, 40(1):185-210, 1993. Google Scholar
  4. M. Beecken, J. Mittmann, and N. Saxena. Algebraic independence and blackbox identity testing. Information &Computation, 222:2-19, 2013. URL: http://dx.doi.org/10.1016/j.ic.2012.10.004.
  5. M. Ben-Or and P. Tiwari. A deterministic algorithm for sparse multivariate polynominal interpolation. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), pages 301-309, 1988. Google Scholar
  6. D. Bshouty and N. H. Bshouty. On interpolating arithmetic read-once formulas with exponentiation. JCSS, 56(1):112-124, 1998. Google Scholar
  7. N. H. Bshouty and R. Cleve. Interpolating arithmetic read-once formulas in parallel. SIAM J. on Computing, 27(2):401-413, 1998. Google Scholar
  8. N. H. Bshouty, T. R. Hancock, and L. Hellerstein. Learning boolean read-once formulas with arbitrary symmetric and constant fan-in gates. JCSS, 50:521-542, 1995. Google Scholar
  9. D. Coppersmith and J. Davenport. Polynomials whose powers are sparse. Acta Arith., 58:79-87, 1991. Google Scholar
  10. D. A. Cox, J. Little, and D. O'Shea. Ideals, varieties, and algorithms - an introduction to computational algebraic geometry and commutative algebra (4. ed.). Undergraduate texts in mathematics. Springer, 2015. Google Scholar
  11. Z. Dvir and R. Mendes de Oliveira. Factors of sparse polynomials are sparse. CoRR, abs/1404.4834, 2014. Google Scholar
  12. Z. Dvir, A. Shpilka, and A. Yehudayoff. Hardness-randomness tradeoffs for bounded depth arithmetic circuits. SIAM J. on Computing, 39(4):1279-1293, 2009. Google Scholar
  13. P. Erdös. On the number of terms of the square of a polynomial. Nieuw Arch. Wisk, 23:63-65, 1949. Google Scholar
  14. S. Gao, E. Kaltofen, and A. G. B. Lauder. Deterministic distinct-degree factorization of polynomials over finite fields. J. Symb. Comput., 38(6):1461-1470, 2004. Google Scholar
  15. K. O. Geddes, S. R. Czapor, and G. Labahn. Algorithms for computer algebra. Kluwer, 1992. Google Scholar
  16. A. Gupta, N. Kayal, and S. V. Lokam. Reconstruction of depth-4 multilinear circuits with top fanin 2. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), pages 625-642, 2012. Full version at http://eccc.hpi-web.de/report 153. Google Scholar
  17. V. Guruswami and M. Sudan. Improved decoding of reed-solomon codes and algebraic-geometry codes. IEEE Transactions on Information Theory, 45(6):1757-1767, 1999. Google Scholar
  18. T. R. Hancock and L. Hellerstein. Learning read-once formulas over fields and extended bases. In Proceedings of the 4th Annual Workshop on Computational Learning Theory (COLT), pages 326-336, 1991. Google Scholar
  19. V. Kabanets and R. Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1-2):1-46, 2004. Google Scholar
  20. E. Kaltofen. Single-factor hensel lifting and its application to the straight-line complexity of certain polynomials. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), pages 443-452, 1987. URL: http://dx.doi.org/10.1145/28395.28443.
  21. E. Kaltofen. Factorization of polynomials given by straight-line programs. In S. Micali, editor, Randomness in Computation, volume 5 of Advances in Computing Research, pages 375-412. JAI Press Inc., Greenwhich, Connecticut, 1989. Google Scholar
  22. E. Kaltofen. Polynomial factorization: a success story. In ISSAC, pages 3-4, 2003. Google Scholar
  23. E. Kaltofen and B. M. Trager. Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators. J. of Symbolic Computation, 9(3):301-320, 1990. Google Scholar
  24. I. Kaplansky. An Introduction to Differential Algebra. Hermann, Paris, 1957. Google Scholar
  25. M. Karchmer, N. Linial, I. Newman, M. E. Saks, and A. Wigderson. Combinatorial characterization of read-once formulae. Discrete Mathematics, 114(1-3):275-282, 1993. Google Scholar
  26. Z. S. Karnin, P. Mukhopadhyay, A. Shpilka, and I. Volkovich. Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in. SIAM J. on Computing, 42(6):2114-2131, 2013. Google Scholar
  27. N. Kayal. Derandomizing some number-theoretic and algebraic algorithms. PhD thesis, Indian Institute of Technology, Kanpur, India, 2007. Google Scholar
  28. N. Kayal. An exponential lower bound for the sum of powers of bounded degree polynomials. Electronic Colloquium on Computational Complexity (ECCC), 19:81, 2012. URL: https://eccc.weizmann.ac.il/report/2012/081/.
  29. A. Klivans and D. Spielman. Randomness efficient identity testing of multivariate polynomials. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), pages 216-223, 2001. Google Scholar
  30. S. Kopparty, S. Saraf, and A. Shpilka. Equivalence of polynomial identity testing and deterministic multivariate polynomial factorization. In Proceedings of the 29th Annual IEEE Conference on Computational Complexity (CCC), pages 169-180, 2014. URL: http://dx.doi.org/10.1109/CCC.2014.25.
  31. A. K. Lenstra, H. W. Lenstr, and L. Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen,, 261(4):515-534, 1982. Google Scholar
  32. R. J. Lipton and N. K. Vishnoi. Deterministic identity testing for multivariate polynomials. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 756-760, 2003. Google Scholar
  33. D. Minahan and I. Volkovich. Complete derandomization of identity testing and reconstruction of read-once formulas. Manuscript, 2016. (submitted). Google Scholar
  34. C. Saha, R. Saptharishi, and N. Saxena. A case of depth-3 identity testing, sparse factorization and duality. Computational Complexity, 22(1):39-69, 2013. URL: http://dx.doi.org/10.1007/s00037-012-0054-4.
  35. S. Saraf and I. Volkovich. Blackbox identity testing for depth-4 multilinear circuits. Combinatorica, 2016. (accepted). Google Scholar
  36. V. Shoup. A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic. In ISSAC, pages 14-21, 1991. Google Scholar
  37. A. Shpilka and I. Volkovich. On the relation between polynomial identity testing and finding variable disjoint factors. In Automata, Languages and Programming, 37th International Colloquium (ICALP), pages 408-419, 2010. Full version at http://eccc.hpi-web.de/report 036. Google Scholar
  38. A. Shpilka and I. Volkovich. On reconstruction and testing of read-once formulas. Theory of Computing, 10:465-514, 2014. Google Scholar
  39. A. Shpilka and I. Volkovich. Read-once polynomial identity testing. Computational Complexity, 24(3):477-532, 2015. Google Scholar
  40. A. Shpilka and A. Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3-4):207-388, 2010. Google Scholar
  41. M. Sudan. Decoding of reed solomon codes beyond the error-correction bound. Journal of Complexity, 13(1):180-193, 1997. Google Scholar
  42. M. Sudan, L. Trevisan, and S. P. Vadhan. Pseudorandom generators without the XOR lemma. J. Comput. Syst. Sci., 62(2):236-266, 2001. URL: http://dx.doi.org/10.1006/jcss.2000.1730.
  43. L. G. Valiant. Negation can be exponentially powerful. Theoretical Computer Science, 12(3):303-314, 1980. Google Scholar
  44. I. Volkovich. Deterministically factoring sparse polynomials into multilinear factors and sums of univariate polynomials. In APPROX-RANDOM, pages 943-958, 2015. Google Scholar
  45. I. Volkovich. Characterizing arithmetic read-once formulae. ACM Transactions on Computation Theory (ToCT), 8(1):2, 2016. URL: http://dx.doi.org/10.1145/2858783.
  46. I. Volkovich. A guide to learning arithmetic circuits. In Proceedings of the 29th Conference on Learning Theory, (COLT), pages 1540-1561, 2016. URL: http://jmlr.org/proceedings/papers/v49/volkovich16.html.
  47. J. von zur Gathen. Who was who in polynomial factorization. In ISSAC, page 2, 2006. Google Scholar
  48. J. von zur Gathen and J. Gerhard. Modern computer algebra. Cambridge University Press, 1999. Google Scholar
  49. J. von zur Gathen and E. Kaltofen. Factoring sparse multivariate polynomials. Journal of Computer and System Sciences, 31(2):265-287, 1985. URL: http://dx.doi.org/10.1016/0022-0000(85)90044-3.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact