Document Open Access Logo

Sets of Linear Forms Which Are Hard to Compute

Authors Michael Kaminski, Igor E. Shparlinski

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.66.pdf
  • Filesize: 0.72 MB
  • 22 pages

Document Identifiers

Author Details

Michael Kaminski
  • Department of Computer Science, Technion - Israel Institute of Technology, Haifa, Israel
Igor E. Shparlinski
  • School of Mathematics and Statistics, University of New South Wales, Sydney, Australia

Funding

  • Shparlinski, Igor E.: During this work, the author was supported by Australian Research Council Grant DP180100201.

Acknowledgements

The authors would like to thank Michel Waldschmidt for the suggestion to use the work of Sert [Alain Sert, 1999] in their argument.

Cite As Get BibTex

Michael Kaminski and Igor E. Shparlinski. Sets of Linear Forms Which Are Hard to Compute. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 66:1-66:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.66

Abstract

We present a uniform description of sets of m linear forms in n variables over the field of rational numbers whose computation requires m(n - 1) additions. Our result is based on bounds on the height of the annihilating polynomials in the Perron theorem and an effective form of the Lindemann-Weierstrass theorem which is due to Sert (1999).

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
Keywords
  • Linear algorithms
  • additive complexity
  • effective Perron theorem
  • effective Lindemann-Weierstrass theorem

Metrics

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

References

  1. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974. Google Scholar
  2. Tom M. Apostol. Mathematical Analysis. Addison-Wesley, Reading, MA, 1963. Second edition. Google Scholar
  3. Enrico Bombieri and Jeffrey. D. Vaaler. On Siegel’s lemma. Inventiones Mathematicaea, 73:11-32, 1983. Google Scholar
  4. Peter Bürgisser, Michael Clausen, and Amin Shokrollahi. Algebraic Complexity Theory. Springer, Berlin, 1997. Google Scholar
  5. Teresa Krick, Luis M. Pardo, and Martín Sombra. Sharp estimates for the arithmetic Nullstellensatz. Duke Mathematical Journal, 9:354-364, 2001. Google Scholar
  6. Serge Lang. Algebraic Number Theory. Addison-Wesley, Reading, MA, 1970. Google Scholar
  7. Jacques Morgenstern. Note on a lower bound on the linear complexity of the fast fourier transform. Journal of the ACM, 20:305-306, 1973. Google Scholar
  8. Oskar Perron. Algebra I (ie Grundlagen). Walter de Gruyter, Berlin, 1927. Google Scholar
  9. Arkadiusz Ploski. Algebraic dependence of polynomials after O. Perron and some applications. In Svetlana Cojocaru, Gerhard Pfister, and Victor Ufnarovski, editors, Computational Commutative and Non-Commutative Algebraic Geometry, volume 196 of NATO Science Series, III: Computer and Systems Sciences, pages 167-173. IOS Press, Amsterdam, 2005. Google Scholar
  10. John E. Savage. An algorithm for the computation of linear forms. SIAM Journal on Computing, 3:150-158, 1974. Google Scholar
  11. Alain Sert. Une version effective du théorème de Lindemann-Weierstrass par les déterminants d'interpolation. Journal of Number Theory, 76:94-119, 1999. Google Scholar
  12. Carl L. Siegel. Über einige Anwendungen diophantischer Approximationen. Abhandlungen der Preussischen Akademie der Wissenschaften. Physikalisch-mathematische Klasse, 1:209-266, 1929. Google Scholar
  13. Volker Strassen. Vermeidung von Divisionen. Journal für Reine und Angewandte Mathematik, 264:184-202, 1973. Google Scholar
  14. Volker Strassen. Polynomials with rational coefficients which are hard to compute. SIAM Journal on Computing, 3:128-149, 1974. Google Scholar
  15. Jeffrey D. Vaaler. The best constant in Siegel’s lemma. Monatshefte für Mathematik, 140:71-89, 2003. Google Scholar
  16. Shmuel Winograd. On the number of multiplications necessary to compute certain functions. Communications od Pure and Applied Mathematics, XXIII:165-179, 1970. Google Scholar
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