Document Open Access Logo

On the Symmetries of and Equivalence Test for Design Polynomials

Authors Nikhil Gupta, Chandan Saha

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.53.pdf
  • Filesize: 0.58 MB
  • 16 pages

Document Identifiers

Author Details

Nikhil Gupta
  • Department of Computer Science and Automation, Indian Institute of Science, India
Chandan Saha
  • Department of Computer Science and Automation, Indian Institute of Science, India

Acknowledgements

We would like to thank Neeraj Kayal, Meena Mahajan for some insightful discussions on the design polynomial family. NG would also like to thank Anuj Tawari for his time in sitting through a few presentations on the proof of Theorem 4. We also thank anonymous reviewers for their comments.

Cite As Get BibTex

Nikhil Gupta and Chandan Saha. On the Symmetries of and Equivalence Test for Design Polynomials. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.53

Abstract

In a Nisan-Wigderson design polynomial (in short, a design polynomial), every pair of monomials share a few common variables. A useful example of such a polynomial, introduced in [Neeraj Kayal et al., 2014], is the following: NW_{d,k}({x}) = sum_{h in F_d[z], deg(h) <= k}{ prod_{i=0}^{d-1}{x_{i, h(i)}}}, where d is a prime, F_d is the finite field with d elements, and k << d. The degree of the gcd of every pair of monomials in NW_{d,k} is at most k. For concreteness, we fix k = ceil[sqrt{d}]. The family of polynomials NW := {NW_{d,k} : d is a prime} and close variants of it have been used as hard explicit polynomial families in several recent arithmetic circuit lower bound proofs. But, unlike the permanent, very little is known about the various structural and algorithmic/complexity aspects of NW beyond the fact that NW in VNP. Is NW_{d,k} characterized by its symmetries? Is it circuit-testable, i.e., given a circuit C can we check efficiently if C computes NW_{d,k}? What is the complexity of equivalence test for NW, i.e., given black-box access to a f in F[{x}], can we check efficiently if there exists an invertible linear transformation A such that f = NW_{d,k}(A * {x})? Characterization of polynomials by their symmetries plays a central role in the geometric complexity theory program. Here, we answer the first two questions and partially answer the third. 
We show that NW_{d,k} is characterized by its group of symmetries over C, but not over R. We also show that NW_{d,k} is characterized by circuit identities which implies that NW_{d,k} is circuit-testable in randomized polynomial time. As another application of this characterization, we obtain the "flip theorem" for NW.
We give an efficient equivalence test for NW in the case where the transformation A is a block-diagonal permutation-scaling matrix. The design of this algorithm is facilitated by an almost complete understanding of the group of symmetries of NW_{d,k}: We show that if A is in the group of symmetries of NW_{d,k} then A = D * P, where D and P are diagonal and permutation matrices respectively. This is proved by completely characterizing the Lie algebra of NW_{d,k}, and using an interplay between the Hessian of NW_{d,k} and the evaluation dimension.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
Keywords
  • Nisan-Wigderson design polynomial
  • characterization by symmetries
  • Lie algebra
  • group of symmetries
  • circuit testability
  • flip theorem
  • equivalence test

Metrics

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

References

  1. Scott Aaronson. P=?NP. Electronic Colloquium on Computational Complexity (ECCC), 24:4, 2017. Google Scholar
  2. Miklós Ajtai. Σ¹₁-formulae on finite structures. Annals of Pure and Applied Logic, 24(1):1-48, 1983. Google Scholar
  3. Noga Alon and Ravi B. Boppana. The monotone circuit complexity of Boolean functions. Combinatorica, 7(1):1-22, 1987. Google Scholar
  4. Albert Atserias. Distinguishing SAT from Polynomial-Size Circuits, through Black-Box Queries. In 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 16-20 July 2006, Prague, Czech Republic, pages 88-95, 2006. Google Scholar
  5. Markus Bläser, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov. Generalized matrix completion and algebraic natural proofs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1193-1206, 2018. Google Scholar
  6. Andrej Bogdanov and Muli Safra. Hardness Amplification for Errorless Heuristics. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 418-426, 2007. Google Scholar
  7. Peter Bürgisser, Christian Ikenmeyer, and Greta Panova. No Occurrence Obstructions in Geometric Complexity Theory. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 386-395, 2016. Google Scholar
  8. Xi Chen, Neeraj Kayal, and Avi Wigderson. Partial Derivatives in Arithmetic Complexity and Beyond. Foundations and Trends in Theoretical Computer Science, 6(1-2):1-138, 2011. Google Scholar
  9. Suryajith Chillara, Nutan Limaye, and Srikanth Srinivasan. Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, pages 21:1-21:15, 2018. Google Scholar
  10. Suryajith Chillara and Partha Mukhopadhyay. Depth-4 Lower Bounds, Determinantal Complexity: A Unified Approach. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5-8, 2014, Lyon, France, pages 239-250, 2014. Google Scholar
  11. Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, and Avi Wigderson. Barriers for Rank Methods in Arithmetic Complexity. In 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, pages 1:1-1:19, 2018. Google Scholar
  12. Michael A. Forbes, Mrinal Kumar, and Ramprasad Saptharishi. Functional Lower Bounds for Arithmetic Circuits and Connections to Boolean Circuit Complexity. In 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, pages 33:1-33:19, 2016. Google Scholar
  13. Michael A. Forbes, Amir Shpilka, and Ben Lee Volk. Succinct hitting sets and barriers to proving algebraic circuits lower bounds. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 653-664, 2017. Google Scholar
  14. Lance Fortnow, Aduri Pavan, and Samik Sengupta. Proving SAT does not have small circuits with an application to the two queries problem. J. Comput. Syst. Sci., 74(3):358-363, 2008. Google Scholar
  15. Hervé Fournier, Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan. Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication. SIAM J. Comput., 44(5):1173-1201, 2015. Google Scholar
  16. Georg Frobenius. Ueber die darstellung der endlichen gruppen durch linearc substitutionen. Sitzungber. der Berliner Akademie, 7:994–1015, 1897. Google Scholar
  17. Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, Circuits, and the Polynomial-Time Hierarchy. In 22nd Annual Symposium on Foundations of Computer Science, Nashville, Tennessee, USA, 28-30 October 1981, pages 260-270, 1981. Google Scholar
  18. Ankit Garg, Nikhil Gupta, Neeraj Kayal, and Chandan Saha. Determinant equivalence test over finite fields and over Q. Electronic Colloquium on Computational Complexity (ECCC), 26:42, 2019. Google Scholar
  19. Fulvio Gesmundo. Gemetric aspects of iterated matrix multiplication. Journal of Algebra, 461:42–64, 2016. Google Scholar
  20. Dima Grigoriev and Marek Karpinski. An Exponential Lower Bound for Depth 3 Arithmetic Circuits. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 577-582, 1998. Google Scholar
  21. Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, and Shubhangi Saraf. Towards an algebraic natural proofs barrier via polynomial identity testing. CoRR, abs/1701.01717, 2017. Google Scholar
  22. Joshua Abraham Grochow. Symmetry and equivalence relations in classical and geometric complexity theory. PhD thesis, Department of Computer Science, The University of Chicago, Chicago, Illinois, 2012. Google Scholar
  23. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Approaching the Chasm at Depth Four. J. ACM, 61(6):33:1-33:16, 2014. Google Scholar
  24. Nikhil Gupta and Chandan Saha. On the symmetries of and equivalence test for design polynomials. ECCC, 2019. URL: https://eccc.weizmann.ac.il/report/2018/164/.
  25. Brian C Hall. Lie Groups, Lie Algebras and Representations An Elementary introduction. Springer, second edition, 2015. Google Scholar
  26. Johan Håstad. Almost Optimal Lower Bounds for Small Depth Circuits. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pages 6-20, 1986. Google Scholar
  27. Jesko Hüttenhain. The Stabilizer of Elementary Symmetric Polynomials. CoRR, abs/1607.08419, 2016. URL: https://arxiv.org/abs/1607.08419.
  28. Christian Ikenmeyer, Ketan D. Mulmuley, and Michael Walter. On vanishing of Kronecker coefficients. Computational Complexity, 26(4):949-992, 2017. Google Scholar
  29. Christian Ikenmeyer and Greta Panova. Rectangular Kronecker Coefficients and Plethysms in Geometric Complexity Theory. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 396-405, 2016. Google Scholar
  30. Neeraj Kayal. Affine projections of polynomials: extended abstract. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 643-662, 2012. Google Scholar
  31. Neeraj Kayal, Nutan Limaye, Chandan Saha, and Srikanth Srinivasan. An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas. SIAM J. Comput., 46(1):307-335, 2017. Google Scholar
  32. Neeraj Kayal, Vineet Nair, Chandan Saha, and Sébastien Tavenas. Reconstruction of Full Rank Algebraic Branching Programs. In 32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia, pages 21:1-21:61, 2017. Google Scholar
  33. Neeraj Kayal and Chandan Saha. Lower Bounds for Depth-Three Arithmetic Circuits with small bottom fanin. Computational Complexity, 25(2):419-454, 2016. Google Scholar
  34. Neeraj Kayal, Chandan Saha, and Ramprasad Saptharishi. A super-polynomial lower bound for regular arithmetic formulas. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 146-153, 2014. Google Scholar
  35. Neeraj Kayal, Chandan Saha, and Sébastien Tavenas. An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 33:1-33:15, 2016. Google Scholar
  36. Neeraj Kayal, Chandan Saha, and Sébastien Tavenas. On the size of homogeneous and of depth four formulas with low individual degree. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 626-632, 2016. Google Scholar
  37. Mrinal Kumar and Ramprasad Saptharishi. An Exponential Lower Bound for Homogeneous Depth-5 Circuits over Finite Fields. In 32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia, pages 31:1-31:30, 2017. Google Scholar
  38. Mrinal Kumar and Shubhangi Saraf. Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic Circuits. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, pages 751-762, 2014. Google Scholar
  39. Mrinal Kumar and Shubhangi Saraf. The limits of depth reduction for arithmetic formulas: it’s all about the top fan-in. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 136-145, 2014. Google Scholar
  40. Mrinal Kumar and Shubhangi Saraf. Arithmetic Circuits with Locally Low Algebraic Rank. In 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, pages 34:1-34:27, 2016. Google Scholar
  41. Mrinal Kumar and Shubhangi Saraf. Sums of Products of Polynomials in Few Variables: Lower Bounds and Polynomial Identity Testing. In 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, pages 35:1-35:29, 2016. Google Scholar
  42. Mrinal Kumar and Shubhangi Saraf. On the Power of Homogeneous Depth 4 Arithmetic Circuits. SIAM J. Comput., 46(1):336-387, 2017. Google Scholar
  43. Richard J. Lipton. New Directions In Testing. In Distributed Computing And Cryptography, Proceedings of a DIMACS Workshop, Princeton, New Jersey, USA, October 4-6, 1989, pages 191-202, 1989. Google Scholar
  44. Marvin Marcus and Francis May. The permanent function. Canadian Journal of Mathematics, 14:177–189, 1962. Google Scholar
  45. Thierry Mignon and Nicolas Ressayre. A quadratic bound for the determinant and permanent problem. International Mathematics Research Notes, 2004(79):4241–4253, 2004. Google Scholar
  46. Ketan Mulmuley. Lower Bounds in a Parallel Model without Bit Operations. SIAM J. Comput., 28(4):1460-1509, 1999. Google Scholar
  47. Ketan Mulmuley. On P vs. NP, Geometric Complexity Theory, and the Flip I: a high level view. CoRR, abs/0709.0748, 2007. Google Scholar
  48. Ketan Mulmuley. Explicit Proofs and The Flip. CoRR, abs/1009.0246, 2010. URL: http://arxiv.org/abs/1009.0246.
  49. Ketan Mulmuley. On P vs. NP and geometric complexity theory: Dedicated to Sri Ramakrishna. J. ACM, 58(2):5:1-5:26, 2011. Google Scholar
  50. Ketan Mulmuley. The GCT program toward the P vs. NP problem. Commun. ACM, 55(6):98-107, 2012. Google Scholar
  51. Ketan Mulmuley and Milind A. Sohoni. Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems. SIAM J. Comput., 31(2):496-526, 2001. Google Scholar
  52. Cody Murray and R. Ryan Williams. Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 890-901, 2018. Google Scholar
  53. Noam Nisan and Avi Wigderson. Hardness vs Randomness. J. Comput. Syst. Sci., 49(2):149-167, 1994. Google Scholar
  54. Noam Nisan and Avi Wigderson. Lower Bounds on Arithmetic Circuits Via Partial Derivatives. Computational Complexity, 6(3):217-234, 1997. Google Scholar
  55. Ran Raz. Multi-linear formulas for permanent and determinant are of super-polynomial size. J. ACM, 56(2):8:1-8:17, 2009. Google Scholar
  56. Ran Raz and Amir Yehudayoff. Lower Bounds and Separations for Constant Depth Multilinear Circuits. Computational Complexity, 18(2):171-207, 2009. Google Scholar
  57. Alexander A. Razborov. Lower bounds on the monotone complexity of some Boolean functions. Soviet Mathematics Doklady, 31:354-357, 1985. Google Scholar
  58. Alexander A. Razborov. Lower bounds on the size of bounded-depth networks over a complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR, 41(4):333-338, 1987. Google Scholar
  59. Alexander A. Razborov and Steven Rudich. Natural Proofs. J. Comput. Syst. Sci., 55(1):24-35, 1997. Google Scholar
  60. Kenneth W. Regan. Understanding the Mulmuley-Sohoni Approach to P vs. NP. Bulletin of the EATCS, 78:86-99, 2002. Google Scholar
  61. Jacob T. Schwartz. Fast Probabilistic Algorithms for Verification of Polynomial Identities. J. ACM, 27(4):701-717, 1980. Google Scholar
  62. Roman Smolensky. Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 77-82, 1987. Google Scholar
  63. Ryan Williams. Nonuniform ACC Circuit Lower Bounds. J. ACM, 61(1):2:1-2:32, 2014. Google Scholar
  64. Richard Zippel. Probabilistic algorithms for sparse polynomials. In Symbolic and Algebraic Computation, EUROSAM '79, An International Symposiumon Symbolic and Algebraic Computation, Marseille, France, June 1979, Proceedings, pages 216-226, 1979. 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