Document Open Access Logo

Towards Blackbox Identity Testing of Log-Variate Circuits

Authors Michael A. Forbes, Sumanta Ghosh, Nitin Saxena

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2018.54.pdf
  • Filesize: 0.52 MB
  • 16 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Theory of computation → Fixed parameter tractability
  • Theory of computation → Pseudorandomness and derandomization
  • Computing methodologies → Algebraic algorithms
  • Mathematics of computing → Combinatoric problems
Keywords
  • hitting-set
  • depth-3
  • diagonal
  • derandomization
  • polynomial identity testing
  • log-variate
  • concentration
  • cone closed
  • basis isolation

Metrics

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

Abstract

Derandomization of blackbox identity testing reduces to extremely special circuit models. After a line of work, it is known that focusing on circuits with constant-depth and constantly many variables is enough (Agrawal,Ghosh,Saxena, STOC'18) to get to general hitting-sets and circuit lower bounds. This inspires us to study circuits with few variables, eg. logarithmic in the size s.
We give the first poly(s)-time blackbox identity test for n=O(log s) variate size-s circuits that have poly(s)-dimensional partial derivative space; eg. depth-3 diagonal circuits (or Sigma wedge Sigma^n). The former model is well-studied (Nisan,Wigderson, FOCS'95) but no poly(s2^n)-time identity test was known before us. We introduce the concept of cone-closed basis isolation and prove its usefulness in studying log-variate circuits. It subsumes the previous notions of rank-concentration studied extensively in the context of ROABP models.

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 54:1-54:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.54

Author Details

Michael A. Forbes
  • University of Illinois at Urbana-Champaign, USA
Sumanta Ghosh
  • Department of Computer Science, IIT Kanpur, India
Nitin Saxena
  • Department of Computer Science, IIT Kanpur, India

References

  1. Manindra Agrawal. Proving lower bounds via pseudo-random generators. In FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, 25th International Conference, Hyderabad, India, December 15-18, 2005, Proceedings, pages 92-105, 2005. Google Scholar
  2. Manindra Agrawal, Sumanta Ghosh, and Nitin Saxena. Bootstrapping variables in algebraic circuits. Technical report, https://www.cse.iitk.ac.in/users/nitin/research.html, 2017. (To appear in 50th ACM Symposium on Theory of Computing (STOC), 2018). Google Scholar
  3. 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
  4. Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. PRIMES is in P. Annals of mathematics, pages 781-793, 2004. Google Scholar
  5. 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
  6. 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
  7. 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
  8. Michael Ben-Or and Prasoon Tiwari. A deterministic algorithm for sparse multivariate polynomial interpolation. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC '88, pages 301-309, 1988. Google Scholar
  9. 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
  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 Proceedings of the 41st International Colloquium on Automata, Languages, and Programming, Part I, volume 8572 of Lecture Notes in Computer Science, pages 417-428. Springer International Publishing, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_35.
  12. Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf. Bipartite perfect matching is in quasi-NC. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 754-763, 2016. Google Scholar
  13. Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf. Guest column: Parallel algorithms for perfect matching. SIGACT News, 48(1):102-109, 2017. Google Scholar
  14. Michael A. Forbes. Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Programs. PhD thesis, Massachusetts Institute of Technology, 2014. Google Scholar
  15. Michael A Forbes. Deterministic divisibility testing via shifted partial derivatives. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 451-465. IEEE, 2015. Google Scholar
  16. Michael A. Forbes, Ankit Gupta, and Amir Shpilka. private communication, 2013. Google Scholar
  17. Michael A. Forbes, Ramprasad Saptharishi, and Amir Shpilka. Pseudorandomness for multilinear read-once algebraic branching programs, in any order. Electronic Colloquium on Computational Complexity (ECCC), 20:132, 2013. Google Scholar
  18. Michael A. Forbes, Ramprasad Saptharishi, and Amir Shpilka. Hitting sets for multilinear read-once algebraic branching programs, in any order. In Symposium on Theory of Computing (STOC), New York, NY, USA, May 31 - June 03, 2014, pages 867-875, 2014. Google Scholar
  19. Michael A. Forbes and Amir Shpilka. On identity testing of tensors, low-rank recovery and compressed sensing. In STOC, pages 163-172, 2012. Google Scholar
  20. 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
  21. Ignacio García-Marco, Pascal Koiran, Timothée Pecatte, and Stéphan Thomassé. On the complexity of partial derivatives. In 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, pages 37:1-37:13, 2017. Google Scholar
  22. Ankit Garg, Leonid Gurvits, Rafael Oliveira, and Avi Wigderson. A deterministic polynomial time algorithm for non-commutative rational identity testing. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, pages 109-117, 2016. Google Scholar
  23. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Arithmetic circuits: A chasm at depth three. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 578-587, 2013. Google Scholar
  24. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Arithmetic circuits: A chasm at depth 3. SIAM Journal on Computing, 45(3):1064-1079, 2016. Google Scholar
  25. 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. (Preliminary version in CCC'16). Google Scholar
  26. Rohit Gurjar, Arpita Korwar, Nitin Saxena, and Thomas Thierauf. Deterministic identity testing for sum of read-once oblivious arithmetic branching programs. Computational Complexity, pages 1-46, 2016. (Conference version in CCC 2015). Google Scholar
  27. 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
  28. Rohit Gurjar, Thomas Thierauf, and Nisheeth K. Vishnoi. Isolating a vertex via lattices: Polytopes with totally unimodular faces. CoRR, abs/1708.02222, 2017. Google Scholar
  29. 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
  30. Stasys Jukna. Extremal Combinatorics: With Applications in Computer Science. Springer Publishing Company, Incorporated, 1st edition, 2010. Google Scholar
  31. Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. In Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, STOC '03, pages 355-364, 2003. Google Scholar
  32. Neeraj Kayal. Algorithms for arithmetic circuits. Electronic Colloquium on Computational Complexity (ECCC), 17:73, 2010. Google Scholar
  33. Neeraj Kayal and Nitin Saxena. Polynomial identity testing for depth 3 circuits. Computational Complexity, 16(2):115-138, 2007. Google Scholar
  34. 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. Google Scholar
  35. 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
  36. 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
  37. 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
  38. Guillaume Lagarde, Guillaume Malod, and Sylvain Perifel. Non-commutative computations: lower bounds and polynomial identity testing. Electronic Colloquium on Computational Complexity (ECCC), 23:94, 2016. Google Scholar
  39. 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
  40. Ketan Mulmuley. Geometric complexity theory V: Efficient algorithms for Noether normalization. Journal of the American Mathematical Society, 30(1):225-309, 2017. Google Scholar
  41. Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani. Matching is as easy as matrix inversion. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC '87, pages 345-354, 1987. Google Scholar
  42. Ketan D Mulmuley. The GCT program toward the P vs. NP problem. Communications of the ACM, 55(6):98-107, 2012. Google Scholar
  43. 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
  44. Noam Nisan and Avi Wigderson. Lower bounds for arithmetic circuits via partial derivatives (preliminary version). In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, 23-25 October 1995, pages 16-25, 1995. Google Scholar
  45. Anurag Pandey, Nitin Saxena, and Amit Sinhababu. Algebraic independence over positive characteristic: New criterion and applications to locally low algebraic rank circuits. In 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Kraków, Poland, pages 74:1-74:15, 2016. (In print, Computational Complexity, 2018). Google Scholar
  46. 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
  47. Ramprasad Saptharishi. personal communication, 2013. Google Scholar
  48. Ramprasad Saptharishi. Unified Approaches to Polynomial Identity Testing and Lower Bounds. PhD thesis, Chennai Mathematical Institute, 2013. Google Scholar
  49. Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity. Technical report, https://github.com/dasarpmar/lowerbounds-survey/, 2016. Google Scholar
  50. 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
  51. Nitin Saxena. Progress on polynomial identity testing. Bulletin of the EATCS, 99:49-79, 2009. Google Scholar
  52. Nitin Saxena. Progress on polynomial identity testing- II. In Perspectives in Computational Complexity, volume 26 of Progress in Computer Science and Applied Logic, pages 131-146. Springer International Publishing, 2014. Google Scholar
  53. 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
  54. J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701-717, 1980. Google Scholar
  55. 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
  56. Avi Wigderson. Low-depth arithmetic circuits: technical perspective. Communications of the ACM, 60(6):91-92, 2017. Google Scholar
  57. 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
  58. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact