LIPIcs.FSTTCS.2019.11.pdf
- Filesize: 0.51 MB
- 14 pages
Document
Constructing Faithful Homomorphisms over Fields of Finite Characteristic
Authors
Prerona Chatterjee 
,
Ramprasad Saptharishi
-
Part of:
Volume:
39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-12-04
File
Document Identifiers
Author Details
Cite As Get BibTex
Prerona Chatterjee and Ramprasad Saptharishi. Constructing Faithful Homomorphisms over Fields of Finite Characteristic. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.FSTTCS.2019.11
Abstract
We study the question of algebraic rank or transcendence degree preserving homomorphisms over finite fields. This concept was first introduced by Beecken et al. [Malte Beecken et al., 2013] and exploited by them and Agrawal et al. [Manindra Agrawal et al., 2016] to design algebraic independence based identity tests using the Jacobian criterion over characteristic zero fields. An analogue of such constructions over finite characteristic fields were unknown due to the failure of the Jacobian criterion over finite characteristic fields. Building on a recent criterion of Pandey, Saxena and Sinhababu [Anurag Pandey et al., 2018], we construct explicit faithful maps for some natural classes of polynomials in fields of positive characteristic, when a certain parameter called the inseparable degree of the underlying polynomials is bounded (this parameter is always 1 in fields of characteristic zero). This presents the first generalisation of some of the results of Beecken, Mittmann and Saxena [Malte Beecken et al., 2013] and Agrawal, Saha, Saptharishi, Saxena [Manindra Agrawal et al., 2016] in the positive characteristic setting.
Subject Classification
ACM Subject Classification
- Theory of computation → Algebraic complexity theory
- Computing methodologies → Symbolic and algebraic manipulation
Keywords
- Faithful Homomorphisms
- Identity Testing
- Algebraic Independence
- Finite characteristic fields
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Manindra Agrawal and Somenath Biswas. Primality and identity testing via Chinese remaindering. J. ACM, 50(4):429-443, 2003. URL: https://doi.org/10.1145/792538.792540.
- Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, and Nitin Saxena. Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-D Occur-k Formulas and Depth-3 Transcendence Degree-k Circuits. SIAM J. Comput., 45(4):1533-1562, 2016. URL: https://doi.org/10.1137/130910725.
- Malte Beecken, Johannes Mittmann, and Nitin Saxena. Algebraic independence and blackbox identity testing. Information and Computing, 222:2-19, 2013. URL: https://doi.org/10.1016/j.ic.2012.10.004.
- Prerona Chatterjee and Ramprasad Saptharishi. Constructing Faithful Homomorphisms over Fields of Finite Characteristic. Electronic Colloquium on Computational Complexity (ECCC), 25:212, 2018. URL: https://eccc.weizmann.ac.il/report/2018/212.
- Richard A. DeMillo and Richard J. Lipton. A Probabilistic Remark on Algebraic Program Testing. Inf. Process. Lett., 7(4):193-195, 1978. URL: https://doi.org/10.1016/0020-0190(78)90067-4.
- Ariel Gabizon and Ran Raz. Deterministic extractors for affine sources over large fields. Combinatorica, 28(4):415-440, 2008. URL: https://doi.org/10.1007/s00493-008-2259-3.
- Zeyu Guo, Nitin Saxena, and Amit Sinhababu. Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity. In Rocco A. Servedio, editor, 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA, volume 102 of LIPIcs, pages 10:1-10:21. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.CCC.2018.10.
- C.G.J. Jacobi. De Determinantibus functionalibus. Journal für die reine und angewandte Mathematik, 22:319-359, 1841. URL: http://eudml.org/doc/147138.
- Neeraj Kayal. The Complexity of the Annihilating Polynomial. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pages 184-193, 2009. URL: https://doi.org/10.1109/CCC.2009.37.
- Adam R. Klivans and Daniel A. Spielman. Randomness efficient identity testing of multivariate polynomials. In Jeffrey Scott Vitter, Paul G. Spirakis, and Mihalis Yannakakis, editors, Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 216-223. ACM, 2001. URL: https://doi.org/10.1145/380752.380801.
- Mrinal Kumar and Shubhangi Saraf. Arithmetic Circuits with Locally Low Algebraic Rank. Theory of Computing, 13(1):1-33, 2017. URL: https://doi.org/10.4086/toc.2017.v013a006.
-
Øystein Ore. Über höhere kongruenzen. Norsk Mat. Forenings Skrifter, 1(7):15, 1922.
-
James G. Oxley. Matroid theory. Oxford University Press, 1992.
- Anurag Pandey, Nitin Saxena, and Amit Sinhababu. Algebraic independence over positive characteristic: New criterion and applications to locally low-algebraic-rank circuits. Computational Complexity, 27(4):617-670, 2018. URL: https://doi.org/10.1007/s00037-018-0167-5.
- Jacob T. Schwartz. Fast Probabilistic Algorithms for Verification of Polynomial Identities. J. ACM, 27(4):701-717, 1980. URL: https://doi.org/10.1145/322217.322225.
- Richard Zippel. Probabilistic algorithms for sparse polynomials. In Symbolic and Algebraic Computation, EUROSAM '79, An International Symposiumon Symbolic and Algebraic Computation, volume 72 of Lecture Notes in Computer Science, pages 216-226. Springer, 1979. URL: https://doi.org/10.1007/3-540-09519-5_73.