Document Open Access Logo

Algebraic Hardness Versus Randomness in Low Characteristic

Author Robert Andrews

PDF
Thumbnail PDF

File

LIPIcs.CCC.2020.37.pdf
  • Filesize: 0.61 MB
  • 32 pages

Document Identifiers

Author Details

Robert Andrews
  • Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL, USA

Funding

Supported by NSF grant CCF-1755921.

Acknowledgements

We would like to thank Michael A. Forbes for many useful comments which helped improve the presentation of this work.

Cite As Get BibTex

Robert Andrews. Algebraic Hardness Versus Randomness in Low Characteristic. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 37:1-37:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.CCC.2020.37

Abstract

We show that lower bounds for explicit constant-variate polynomials over fields of characteristic p > 0 are sufficient to derandomize polynomial identity testing over fields of characteristic p. In this setting, existing work on hardness-randomness tradeoffs for polynomial identity testing requires either the characteristic to be sufficiently large or the notion of hardness to be stronger than the standard syntactic notion of hardness used in algebraic complexity. Our results make no restriction on the characteristic of the field and use standard notions of hardness.
We do this by combining the Kabanets-Impagliazzo generator with a white-box procedure to take p-th roots of circuits computing a p-th power over fields of characteristic p. When the number of variables appearing in the circuit is bounded by some constant, this procedure turns out to be efficient, which allows us to bypass difficulties related to factoring circuits in characteristic p.
We also combine the Kabanets-Impagliazzo generator with recent "bootstrapping" results in polynomial identity testing to show that a sufficiently-hard family of explicit constant-variate polynomials yields a near-complete derandomization of polynomial identity testing. This result holds over fields of both zero and positive characteristic and complements a recent work of Guo, Kumar, Saptharishi, and Solomon, who obtained a slightly stronger statement over fields of characteristic zero.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • Polynomial identity testing
  • hardness versus randomness
  • low characteristic

Metrics

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

References

  1. Manindra Agrawal and Somenath Biswas. Primality and identity testing via Chinese remaindering. J. ACM, 50(4):429-443, 2003. Preliminary version in the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1999). URL: https://doi.org/10.1145/792538.792540.
  2. Manindra Agrawal, Sumanta Ghosh, and Nitin Saxena. Bootstrapping variables in algebraic circuits. Proc. Natl. Acad. Sci. USA, 116(17):8107-8118, 2019. Preliminary version in the 50th Annual ACM Symposium on Theory of Computing (STOC 2018). URL: https://doi.org/10.1073/pnas.1901272116.
  3. Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. PRIMES is in P. Ann. of Math. (2), 160(2):781-793, 2004. URL: https://doi.org/10.4007/annals.2004.160.781.
  4. Manindra 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 2008), pages 67-75, 2008. URL: https://doi.org/10.1109/FOCS.2008.32.
  5. Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. Complexity and real computation. Springer-Verlag, New York, 1998. With a foreword by Richard M. Karp. URL: https://doi.org/10.1007/978-1-4612-0701-6.
  6. Manuel Blum, Ashok K. Chandra, and Mark N. Wegman. Equivalence of free Boolean graphs can be decided probabilistically in polynomial time. Inform. Process. Lett., 10(2):80-82, 1980. URL: https://doi.org/10.1016/S0020-0190(80)90078-2.
  7. Nicolas Bourbaki. Algebra. II. Chapters 4-7. Elements of Mathematics (Berlin). Springer-Verlag, Berlin, 1990. Translated from the French by P. M. Cohn and J. Howie. Google Scholar
  8. Peter Bürgisser. Completeness and reduction in algebraic complexity theory, volume 7 of Algorithms and Computation in Mathematics. Springer-Verlag, Berlin, 2000. URL: https://doi.org/10.1007/978-3-662-04179-6.
  9. Peter Bürgisser. On defining integers and proving arithmetic circuit lower bounds. Comput. Complexity, 18(1):81-103, 2009. Preliminary version in the 24th Symposium on Theoretical Aspects of Computer Science (STACS 2007). URL: https://doi.org/10.1007/s00037-009-0260-x.
  10. Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi. Algebraic complexity theory, volume 315 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 1997. With the collaboration of Thomas Lickteig. URL: https://doi.org/10.1007/978-3-662-03338-8.
  11. Marco L. Carmosino, Russell Impagliazzo, Shachar Lovett, and Ivan Mihajlin. Hardness amplification for non-commutative arithmetic circuits. In Proceedings of the 33rd Annual Computational Complexity Conference (CCC 2018), volume 102 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1-12:16. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.CCC.2018.12.
  12. Chi-Ning Chou, Mrinal Kumar, and Noam Solomon. Hardness vs randomness for bounded depth arithmetic circuits. In Proceedings of the 33rd Annual Computational Complexity Conference (CCC 2018), volume 102 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1-13:17. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.CCC.2018.13.
  13. Zeev Dvir, Amir Shpilka, and Amir Yehudayoff. Hardness-randomness tradeoffs for bounded depth arithmetic circuits. SIAM J. Comput., 39(4):1279-1293, 2009. Preliminary version in the 40th Annual ACM Symposium on Theory of Computing (STOC 2008). URL: https://doi.org/10.1137/080735850.
  14. Michael A. Forbes, Sumanta Ghosh, and Nitin Saxena. Towards blackbox identity testing of log-variate circuits. In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 54:1-54:16. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.54.
  15. Dima Grigoriev and Marek Karpinski. An exponential lower bound for depth 3 arithmetic circuits. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC 1998), pages 577-582. ACM, New York, 1998. Google Scholar
  16. Dima Grigoriev and Alexander Razborov. Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields. Appl. Algebra Engrg. Comm. Comput., 10(6):465-487, 2000. Preliminary version in the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1998). URL: https://doi.org/10.1007/s002009900021.
  17. Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, and Noam Solomon. Derandomization from algebraic hardness: Treading the borders. In Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2019), pages 147-157, 2019. URL: https://doi.org/10.1109/FOCS.2019.00018.
  18. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Arithmetic circuits: a chasm at depth 3. SIAM J. Comput., 45(3):1064-1079, 2016. Preliminary version in the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013). URL: https://doi.org/10.1137/140957123.
  19. Pavel Hrubeš and Amir Yehudayoff. Arithmetic complexity in ring extensions. Theory of Computing, 7(8):119-129, 2011. URL: https://doi.org/10.4086/toc.2011.v007a008.
  20. Russell Impagliazzo and Avi Wigderson. P = BPP if E requires exponential circuits: derandomizing the XOR lemma. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC 1997), pages 220-229. ACM, New York, 1997. Google Scholar
  21. Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complexity, 13(1-2):1-46, 2004. Preliminary version in the 35th Annual ACM Symposium on Theory of Computing (STOC 2003). URL: https://doi.org/10.1007/s00037-004-0182-6.
  22. Erich Kaltofen. Factorization of polynomials given by straight-line programs. Advances in Computing Research, 5, 1989. Google Scholar
  23. Richard M. Karp, Eli Upfal, and Avi Wigderson. Constructing a perfect matching is in Random NC. Combinatorica, 6(1):35-48, 1986. Preliminary version in the 17th Annual ACM Symposium on Theory of Computing (STOC 1985). URL: https://doi.org/10.1007/BF02579407.
  24. Pascal Koiran. Arithmetic circuits: the chasm at depth four gets wider. Theoret. Comput. Sci., 448:56-65, 2012. URL: https://doi.org/10.1016/j.tcs.2012.03.041.
  25. Mrinal Kumar and Ramprasad Saptharishi. An exponential lower bound for homogeneous depth-5 circuits over finite fields. In Proceedings of the 32rd Annual Computational Complexity Conference (CCC 2017), volume 79 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1-30:30. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.CCC.2017.31.
  26. Mrinal Kumar and Ramprasad Saptharishi. Hardness-randomness tradeoffs for algebraic computation. Bull. Eur. Assoc. Theor. Comput. Sci., 129:56-87, 2019. Google Scholar
  27. Mrinal Kumar, Ramprasad Saptharishi, and Anamay Tengse. Near-optimal bootstrapping of hitting sets for algebraic circuits. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), pages 639-646. SIAM, Philadelphia, PA, 2019. URL: https://doi.org/10.1137/1.9781611975482.40.
  28. Richard J. Lipton. Straight-line complexity and integer factorization. In Algorithmic number theory (Ithaca, NY, 1994), volume 877 of Lecture Notes in Comput. Sci., pages 71-79. Springer, Berlin, 1994. URL: https://doi.org/10.1007/3-540-58691-1_45.
  29. László Lovász. On determinants, matchings, and random algorithms. In Fundamentals of computation theory (Proc. Conf. Algebraic, Arith. and Categorical Methods in Comput. Theory, Berlin/Wendisch-Rietz, 1979), volume 2 of Math. Res., pages 565-574. Akademie-Verlag, Berlin, 1979. Google Scholar
  30. Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7(1):105-113, 1987. Preliminary version in the 19th Annual ACM Symposium on Theory of Computing (STOC 1987). URL: https://doi.org/10.1007/BF02579206.
  31. Noam Nisan and Avi Wigderson. Hardness vs. randomness. J. Comput. System Sci., 49(2):149-167, 1994. URL: https://doi.org/10.1016/S0022-0000(05)80043-1.
  32. Ran Raz. Tensor-rank and lower bounds for arithmetic formulas. J. ACM, 60(6):Art. 40, 15, 2013. Preliminary version in the 42nd Annual ACM Symposium on Theory of Computing (STOC 2010). URL: https://doi.org/10.1145/2535928.
  33. Steven Roman. Field theory, volume 158 of Graduate Texts in Mathematics. Springer, New York, 2 edition, 2006. Google Scholar
  34. Nitin Saxena. Progress on polynomial identity testing. Bull. Eur. Assoc. Theor. Comput. Sci., 99:49-79, 2009. Google Scholar
  35. Nitin Saxena. Progress on polynomial identity testing ii. In Proceedings of the Workshop celebrating Somenath Biswas' 60th Birthday, pages 131-146, 2014. Google Scholar
  36. Ronen Shaltiel and Christopher Umans. Simple extractors for all min-entropies and a new pseudorandom generator. J. ACM, 52(2):172-216, 2005. Preliminary version in the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2001). URL: https://doi.org/10.1145/1059513.1059516.
  37. Adi Shamir. Factoring numbers in O(log n) arithmetic steps. Inform. Process. Lett., 8(1):28-31, 1979. URL: https://doi.org/10.1016/0020-0190(79)90087-5.
  38. Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: a survey of recent results and questions. Found. Trends Theor. Comput. Sci., 5(3-4):207-388, 2010. URL: https://doi.org/10.1561/0400000039.
  39. Sébastien Tavenas. Improved bounds for reduction to depth 4 and depth 3. Inform. and Comput., 240:2-11, 2015. URL: https://doi.org/10.1016/j.ic.2014.09.004.
  40. Christopher Umans. Pseudo-random generators for all hardnesses. J. Comput. System Sci., 67(2):419-440, 2003. Preliminary version in the 34th Annual ACM Symposium on Theory of Computing (STOC 2002). URL: https://doi.org/10.1016/S0022-0000(03)00046-1.
  41. Ryan Williams. Finding paths of length k in O^*(2^k) time. Inform. Process. Lett., 109(6):315-318, 2009. URL: https://doi.org/10.1016/j.ipl.2008.11.004.
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