Document Open Access Logo

Improved Hitting Set for Orbit of ROABPs

Authors Vishwas Bhargava, Sumanta Ghosh

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.30.pdf
  • Filesize: 0.86 MB
  • 23 pages

Document Identifiers

Author Details

Vishwas Bhargava
  • Department of Computer Science, Rutgers University, Piscataway, NJ, USA
Sumanta Ghosh
  • Department of Computer Science, IIT Bombay, India

Funding

  • Bhargava, Vishwas: Research supported in part by the Simons Collaboration on Algorithms and Geometry and NSF grant CCF-1909683.

Acknowledgements

The authors would like to thank the anonymous referees for useful comments that improved the presentation of the results.

Cite AsGet BibTex

Vishwas Bhargava and Sumanta Ghosh. Improved Hitting Set for Orbit of ROABPs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 30:1-30:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.30

Abstract

The orbit of an n-variate polynomial f(x) over a field 𝔽 is the set {f(Ax+b) ∣ A ∈ GL(n, 𝔽) and b ∈ 𝔽ⁿ}, and the orbit of a polynomial class is the union of orbits of all the polynomials in it. In this paper, we give improved constructions of hitting-sets for the orbit of read-once oblivious algebraic branching programs (ROABPs) and a related model. Over fields with characteristic zero or greater than d, we construct a hitting set of size (ndw)^{O(w²log n⋅ min{w², dlog w})} for the orbit of ROABPs in unknown variable order where d is the individual degree and w is the width of ROABPs. We also give a hitting set of size (ndw)^{O(min{w²,dlog w})} for the orbit of polynomials computed by w-width ROABPs in any variable order. Our hitting sets improve upon the results of Saha and Thankey [Chandan Saha and Bhargav Thankey, 2021] who gave an (ndw)^{O(dlog w)} size hitting set for the orbit of commutative ROABPs (a subclass of any-order ROABPs) and (nw)^{O(w⁶log n)} size hitting set for the orbit of multilinear ROABPs. Designing better hitting sets in large individual degree regime, for instance d > n, was asked as an open problem by [Chandan Saha and Bhargav Thankey, 2021] and this work solves it in small width setting. We prove some new rank concentration results by establishing low-cone concentration for the polynomials over vector spaces, and they strengthen some previously known low-support based rank concentrations shown in [Michael A. Forbes et al., 2013]. These new low-cone concentration results are crucial in our hitting set construction, and may be of independent interest. To the best of our knowledge, this is the first time when low-cone rank concentration has been used for designing hitting sets.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Computing methodologies → Algebraic algorithms
Keywords
  • Hitting Set
  • Low Cone Concentration
  • Orbits
  • PIT
  • ROABP

Metrics

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

Related Versions

References

  1. Manindra Agrawal, Rohit Gurjar, Arpita Korwar, and Nitin Saxena. Hitting-sets for ROABP and sum of set-multilinear circuits. SIAM Journal on Computing, 44(3):669-697, 2015. Google Scholar
  2. Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. PRIMES is in P. Annals of mathematics, pages 781-793, 2004. Google Scholar
  3. Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, and Nitin Saxena. Jacobian hits circuits: hitting-sets, lower bounds for depth-d occur-k formulas & depth-3 transcendence degree-k circuits. In STOC, pages 599-614, 2012. Google Scholar
  4. Manindra Agrawal, Chandan Saha, and Nitin Saxena. Quasi-polynomial hitting-set for set-depth-Δ formulas. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 321-330, 2013. Google Scholar
  5. M. Beecken, J. Mittmann, and N. Saxena. Algebraic Independence and Blackbox Identity Testing. Inf. Comput., 222:2-19, 2013. (Conference version in ICALP 2011). Google Scholar
  6. Michael Ben-Or and Prasoon Tiwari. A deterministic algorithm for sparse multivariate polynominal interpolation (extended abstract). In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pages 301-309, 1988. URL: https://doi.org/10.1145/62212.62241.
  7. Chi-Ning Chou, Mrinal Kumar, and Noam Solomon. Hardness vs randomness for bounded depth arithmetic circuits. In 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA, pages 13:1-13:17, 2018. URL: https://doi.org/10.4230/LIPIcs.CCC.2018.13.
  8. David A. Cox, John Little, and Donal O'Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer Publishing Company, Incorporated, 4th edition, 2015. Google Scholar
  9. Rafael Mendes de Oliveira, Amir Shpilka, and Ben Lee Volk. Subexponential size hitting sets for bounded depth multilinear formulas. In 30th Conference on Computational Complexity, CCC 2015, June 17-19, 2015, Portland, Oregon, USA, pages 304-322, 2015. URL: https://doi.org/10.4230/LIPIcs.CCC.2015.304.
  10. Richard A. Demillo and Richard J. Lipton. A probabilistic remark on algebraic program testing. Information Processing Letters, 7(4):193-195, 1978. Google Scholar
  11. Zeev Dvir, Rafael Mendes de Oliveira, and Amir Shpilka. Testing Equivalence of Polynomials under Shifts. In 41st International Colloquium on Automata, Languages, and Programming, Part I, volume 8572 of Lecture Notes in Computer Science, pages 417-428, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_35.
  12. Zeev Dvir and Amir Shpilka. Locally decodable codes with two queries and polynomial identity testing for depth 3 circuits. SIAM J. Comput., 36(5):1404-1434, 2007. URL: https://doi.org/10.1137/05063605X.
  13. Zeev Dvir, Amir Shpilka, and Amir Yehudayoff. Hardness-randomness tradeoffs for bounded depth arithmetic circuits. SIAM J. Comput., 39(4):1279-1293, 2009. URL: https://doi.org/10.1137/080735850.
  14. Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf. Bipartite perfect matching is in quasi-NC. In 48th Annual ACM Symposium on Theory of Computing, pages 754-763, 2016. Google Scholar
  15. Michael A Forbes. Deterministic divisibility testing via shifted partial derivatives. In 56th Annual Symposium on Foundations of Computer Science, pages 451-465, 2015. Google Scholar
  16. Michael A. Forbes, Sumanta Ghosh, and Nitin Saxena. Towards blackbox identity testing of log-variate circuits. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 54:1-54:16, 2018. Google Scholar
  17. Michael A. Forbes, Ramprasad Saptharishi, and Amir Shpilka. Pseudorandomness for multilinear read-once algebraic branching programs, in any order. Electron. Colloquium Comput. Complex., 20:132, 2013. Conference version is accepted in STOC 2014. URL: http://eccc.hpi-web.de/report/2013/132.
  18. Michael A Forbes and Amir Shpilka. Explicit noether normalization for simultaneous conjugation via polynomial identity testing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 527-542. Springer, 2013. Google Scholar
  19. Michael A. Forbes and Amir Shpilka. Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 243-252. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/FOCS.2013.34.
  20. Zeyu Guo and Rohit Gurjar. Improved explicit hitting-sets for roabps. In Jaroslaw Byrka and Raghu Meka, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020, August 17-19, 2020, Virtual Conference, volume 176 of LIPIcs, pages 4:1-4:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.4.
  21. Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, and Noam Solomon. Derandomization from algebraic hardness. Electronic Colloquium on Computational Complexity (ECCC), 26:65, 2019. Preliminary version in FOCS 2019. URL: https://eccc.weizmann.ac.il/report/2019/065/.
  22. Rohit Gurjar, Arpita Korwar, and Nitin Saxena. Identity testing for constant-width, and any-order, read-once oblivious arithmetic branching programs. Theory of Computing, 13(2):1-21, 2017. Google Scholar
  23. Rohit Gurjar, Arpita Korwar, Nitin Saxena, and Thomas Thierauf. Deterministic identity testing for sum of read-once oblivious arithmetic branching programs. In 30th Conference on Computational Complexity, CCC 2015, June 17-19, 2015, Portland, Oregon, USA, pages 323-346, 2015. URL: https://doi.org/10.4230/LIPIcs.CCC.2015.323.
  24. Rohit Gurjar and Thomas Thierauf. Linear matroid intersection is in quasi-nc. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 821-830, 2017. Google Scholar
  25. Joos Heintz and Claus-Peter Schnorr. Testing polynomials which are easy to compute (extended abstract). In Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA, pages 262-272, 1980. Google Scholar
  26. Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational 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.
  27. Zohar Shay Karnin and Amir Shpilka. Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in. Combinatorica, 31(3):333-364, 2011. URL: https://doi.org/10.1007/s00493-011-2537-3.
  28. Neeraj Kayal and Shubhangi Saraf. Blackbox polynomial identity testing for depth 3 circuits. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 198-207, 2009. URL: https://doi.org/10.1109/FOCS.2009.67.
  29. Neeraj Kayal and Nitin Saxena. Polynomial identity testing for depth 3 circuits. Computational Complexity, 16(2):115-138, 2007. Google Scholar
  30. Adam R. Klivans and Daniel A. Spielman. Randomness efficient identity testing of multivariate polynomials. In Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 216-223, 2001. URL: https://doi.org/10.1145/380752.380801.
  31. Swastik Kopparty, Shubhangi Saraf, and Amir Shpilka. Equivalence of polynomial identity testing and deterministic multivariate polynomial factorization. In IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014, pages 169-180, 2014. Google Scholar
  32. Mrinal Kumar and Shubhangi Saraf. Arithmetic circuits with locally low algebraic rank. Theory of Computing, 13(1):1-33, 2017. Preliminary version in the 31st Conference on Computational Complexity (CCC), 2016. URL: https://doi.org/10.4086/toc.2017.v013a006.
  33. Mrinal Kumar and Ben Lee Volk. A polynomial degree bound on equations for non-rigid matrices and small linear circuits. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference, volume 185 of LIPIcs, pages 9:1-9:9. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ITCS.2021.9.
  34. Richard J. Lipton and Nisheeth K. Vishnoi. Deterministic identity testing for multivariate polynomials. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland, USA., pages 756-760, 2003. Google Scholar
  35. László Lovász. On determinants, matchings, and random algorithms. In FCT, volume 79, pages 565-574, 1979. Google Scholar
  36. Dori Medini and Amir Shpilka. Hitting sets and reconstruction for dense orbits in vp_e and ΣΠΣ circuits. CoRR, abs/2102.05632, 2021. URL: http://arxiv.org/abs/2102.05632.
  37. Daniel Minahan and Ilya Volkovich. Complete derandomization of identity testing and reconstruction of read-once formulas. In Ryan O'Donnell, editor, 32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia, volume 79 of LIPIcs, pages 32:1-32:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.CCC.2017.32.
  38. Ketan D. Mulmuley. Geometric complexity theory V: Equivalence between blackbox derandomization of polynomial identity testing and derandomization of Noether’s normalization lemma. In FOCS, pages 629-638, 2012. Google Scholar
  39. Noam Nisan and Avi Wigderson. Lower bounds on arithmetic circuits via partial derivatives. Computational Complexity, 6(3):217-234, 1997. Preliminary version in the 36th Annual Symposium on Foundations of Computer Science (FOCS), 1995. URL: https://doi.org/10.1007/BF01294256.
  40. 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. Preliminary version in the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS), 2016. URL: https://doi.org/10.1007/s00037-018-0167-5.
  41. Ran Raz and Amir Shpilka. Deterministic polynomial identity testing in non-commutative models. Computational Complexity, 14(1):1-19, 2005. URL: https://doi.org/10.1007/s00037-005-0188-8.
  42. Chandan Saha, Ramprasad Saptharishi, and Nitin Saxena. A case of depth-3 identity testing, sparse factorization and duality. Computational Complexity, 22(1):39-69, 2013. Google Scholar
  43. Chandan Saha and Bhargav Thankey. Hitting sets for orbits of circuit classes and polynomial families. Electron. Colloquium Comput. Complex., 28:15, 2021. URL: https://eccc.weizmann.ac.il/report/2021/015.
  44. Nitin Saxena. Diagonal circuit identity testing and lower bounds. In ICALP, volume 5125 of Lecture Notes in Computer Science, pages 60-71. Springer, 2008. Google Scholar
  45. Nitin Saxena. Progress on polynomial identity testing. Bulletin of the EATCS, 99:49-79, 2009. Google Scholar
  46. Nitin Saxena and C. Seshadhri. An almost optimal rank bound for depth-3 identities. SIAM J. Comput., 40(1):200-224, 2011. URL: https://doi.org/10.1137/090770679.
  47. Nitin Saxena and C. Seshadhri. Blackbox identity testing for bounded top-fanin depth-3 circuits: The field doesn't matter. SIAM Journal on Computing, 41(5):1285-1298, 2012. Google Scholar
  48. Nitin Saxena and C. Seshadhri. From sylvester-gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuits. J. ACM, 60(5):33:1-33:33, 2013. URL: https://doi.org/10.1145/2528403.
  49. J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701-717, 1980. Google Scholar
  50. Adi Shamir. Ip=pspace. In 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume I, pages 11-15, 1990. URL: https://doi.org/10.1109/FSCS.1990.89519.
  51. Amir Shpilka and Ilya Volkovich. Improved polynomial identity testing for read-once formulas. In Irit Dinur, Klaus Jansen, Joseph Naor, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings, volume 5687 of Lecture Notes in Computer Science, pages 700-713. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-03685-9_52.
  52. Amir Shpilka and Ilya Volkovich. Read-once polynomial identity testing. Comput. Complex., 24(3):477-532, 2015. URL: https://doi.org/10.1007/s00037-015-0105-8.
  53. Amir Shpilka and Amir 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
  54. Ola Svensson and Jakub Tarnawski. The matching problem in general graphs is in quasi-nc. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 696-707, 2017. URL: https://doi.org/10.1109/FOCS.2017.70.
  55. W. T. Tutte. The factorization of linear graphs. Journal of the London Mathematical Society, s1-22(2):107-111, 1947. Google Scholar
  56. Jiang Zeng. A bijective proof of Muir’s identity and the Cauchy-Binet formula. Linear Algebra and its Applications, 184:79-82, 1993. Google Scholar
  57. Richard Zippel. Probabilistic algorithms for sparse polynomials. In Proceedings of the International Symposium on Symbolic and Algebraic Computation, EUROSAM '79, 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 Imprint Privacy Contact