Document Open Access Logo

Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs

Authors Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

PDF
Thumbnail PDF

File

LIPIcs.CCC.2016.30.pdf
  • Filesize: 0.62 MB
  • 25 pages

Document Identifiers

Author Details

Matthew Anderson
Michael A. Forbes
Ramprasad Saptharishi
Amir Shpilka
Ben Lee Volk

Cite As Get BibTex

Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk. Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 30:1-30:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.CCC.2016.30

Abstract

Read-k oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ROABPs). In this work, we give an exponential lower bound of exp(n/k^{O(k)}) on the width of any read-k oblivious ABP computing some explicit multilinear polynomial f that is computed by a polynomial size depth-3 circuit. We also study the polynomial identity testing (PIT) problem for this model and obtain a white-box subexponential-time PIT algorithm. The algorithm runs in time 2^{~O(n^{1-1/2^{k-1}})} and needs white box access only to know the order in which the variables appear in the ABP.

Subject Classification

Keywords
  • Algebraic Complexity
  • Lower Bounds
  • Derandomization
  • Polynomial Identity Testing

Metrics

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

References

  1. Manindra Agrawal. Proving Lower Bounds Via Pseudo-random Generators. In Proceedings of the \nth\intcalcSub20051980 International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2005), pages 92-105, 2005. URL: http://dx.doi.org/10.1007/11590156_6.
  2. Manindra Agrawal, Rohit Gurjar, Arpita Korwar, and Nitin Saxena. Hitting-sets for ROABP and sum of set-multilinear circuits. SIAM Journal of Computing, 44(3):669-697, 2015. URL: http://dx.doi.org/10.1137/140975103.
  3. Manindra Agrawal and V. Vinay. Arithmetic circuits: A chasm at depth four. In Proceedings of the \ifnumcomp2008<1966\nth\intcalcSub20081959 Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 2008)\ifnumcomp2008<1975\nth\intcalcSub20081959 Annual Symposium on Switching and Automata Theory (SWAT 2008)\nth\intcalcSub20081959 Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), pages 67-75, 2008. URL: http://dx.doi.org/10.1109/FOCS.2008.32.
  4. Martin Aigner and Günter M. Ziegler. Proofs from THE BOOK. Springer, 2004. URL: http://dx.doi.org/10.1007/978-3-662-44205-0.
  5. Miklós Ajtai. A non-linear time lower bound for boolean branching programs. Theory of Computing, 1(1):149-176, 2005. Preliminary version in the \ifnumcomp1999<1966\nth\intcalcSub19991959 Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 1999)\ifnumcomp1999<1975\nth\intcalcSub19991959 Annual Symposium on Switching and Automata Theory (SWAT 1999)\nth\intcalcSub19991959 Annual IEEE Symposium on Foundations of Computer Science (FOCS 1999). URL: http://dx.doi.org/10.4086/toc.2005.v001a008.
  6. Noga Alon, Zoltán Füredi, and Meir Katchalski. Separating pairs of points by standard boxes. European Journal of Combinatorics, 6(3):205-210, 1985. URL: http://dx.doi.org/10.1016/S0195-6698(85)80028-7.
  7. Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk. Identity testing and lower bounds for read-k oblivious algebraic branching programs. Electronic Colloquium on Computational Complexity (ECCC), 22:184, 2015. URL: http://eccc.hpi-web.de/report/2015/184.
  8. Matthew Anderson, Dieter van Melkebeek, and Ilya Volkovich. Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae. In Proceedings of the \ifnumcomp2011<1996\nth\intcalcSub20111985 Annual Structure in Complexity Theory Conference (Structures 2011)\ifnumcomp2011<2015\nth\intcalcSub20111985 Annual IEEE Conference on Computational Complexity (CCC 2011)\nth\intcalcSub20111985 Annual Computational Complexity Conference (CCC 2011), pages 273-282, 2011. Google Scholar
  9. Vikraman Arvind and Sathasivam Raja. Some lower bound results for set-multilinear arithmetic computations. Electronic Colloquium on Computational Complexity (ECCC), 22:176, 2015. URL: http://eccc.hpi-web.de/report/2015/176/.
  10. László Babai, Péter Hajnal, Endre Szemerédi, and György Turán. A lower bound for read-once-only branching programs. J. Comput. Syst. Sci., 35(2):153-162, 1987. URL: http://dx.doi.org/10.1016/0022-0000(87)90010-9.
  11. Paul Beame, Michael E. Saks, Xiaodong Sun, and Erik Vee. Time-space trade-off lower bounds for randomized computation of decision problems. J. ACM, 50(2):154-195, 2003. URL: http://dx.doi.org/10.1145/636865.636867.
  12. Andrej Bogdanov, Zeev Dvir, Elad Verbin, and Amir Yehudayoff. Pseudorandomness for width-2 branching programs. Theory of Computing, 9:283-293, 2013. URL: http://dx.doi.org/10.4086/toc.2013.v009a007.
  13. Andrej Bogdanov, Periklis A. Papakonstantinou, and Andrew Wan. Pseudorandomness for read-once formulas. In Proceedings of the \ifnumcomp2011<1966\nth\intcalcSub20111959 Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 2011)\ifnumcomp2011<1975\nth\intcalcSub20111959 Annual Symposium on Switching and Automata Theory (SWAT 2011)\nth\intcalcSub20111959 Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011), pages 240-246, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.57.
  14. Allan Borodin, Alexander A. Razborov, and Roman Smolensky. On lower bounds for read-k-times branching programs. Computational Complexity, 3:1-18, 1993. URL: http://dx.doi.org/10.1007/BF01200404.
  15. Mark Braverman, Anup Rao, Ran Raz, and Amir Yehudayoff. Pseudorandom generators for regular branching programs. SIAM J. Comput., 43(3):973-986, 2014. URL: http://dx.doi.org/10.1137/120875673.
  16. Anindya De. Pseudorandomness for permutation and regular branching programs. In Proceedings of the \ifnumcomp2011<1996\nth\intcalcSub20111985 Annual Structure in Complexity Theory Conference (Structures 2011)\ifnumcomp2011<2015\nth\intcalcSub20111985 Annual IEEE Conference on Computational Complexity (CCC 2011)\nth\intcalcSub20111985 Annual Computational Complexity Conference (CCC 2011), pages 221-231, 2011. URL: http://dx.doi.org/10.1109/CCC.2011.23.
  17. Richard A. DeMillo and Richard J. Lipton. A Probabilistic Remark on Algebraic Program Testing. Information Processing Letters, 7(4):193-195, 1978. URL: http://dx.doi.org/10.1016/0020-0190(78)90067-4.
  18. 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. Preliminary version in the \nth\intcalcSub20051968 Annual ACM Symposium on Theory of Computing (STOC 2005). URL: http://dx.doi.org/10.1137/05063605X.
  19. Zeev Dvir, Amir Shpilka, and Amir Yehudayoff. Hardness-randomness tradeoffs for bounded depth arithmetic circuits. SIAM J. Comput., 39(4):1279-1293, 2009. URL: http://dx.doi.org/10.1137/080735850.
  20. Paul Erdős and George Szekeres. A combinatorial problem in geometry. Compositio Math., 2:463-470, 1935. URL: http://dx.doi.org/10.1007/978-0-8176-4842-8_3.
  21. Michael Forbes. Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Programs. PhD thesis, Massachusetts Institute of Technology, 2014. URL: http://hdl.handle.net/1721.1/89843.
  22. Michael A. Forbes, Ramprasad Saptharishi, and Amir Shpilka. Hitting sets for multilinear read-once algebraic branching programs, in any order. In Proceedings of the \nth\intcalcSub20141968 Annual ACM Symposium on Theory of Computing (STOC 2014), pages 867-875, 2014. URL: http://dx.doi.org/10.1145/2591796.2591816.
  23. Michael A. Forbes and Amir Shpilka. Explicit noether normalization for simultaneous conjugation via polynomial identity testing. In Proceedings of the \nth\intcalcSub20131996 International Workshop on Randomization and Computation (RANDOM 2013), volume 8096 of Lecture Notes in Computer Science, pages 527-542. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40328-6_37.
  24. Michael A. Forbes and Amir Shpilka. Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In Proceedings of the \ifnumcomp2013<1966\nth\intcalcSub20131959 Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 2013)\ifnumcomp2013<1975\nth\intcalcSub20131959 Annual Symposium on Switching and Automata Theory (SWAT 2013)\nth\intcalcSub20131959 Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), pages 243-252, 2013. Full version at http://arxiv.org/abs/1209.2408. URL: http://dx.doi.org/10.1109/FOCS.2013.34.
  25. Hervé Fournier, Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan. Lower bounds for depth 4 formulas computing iterated matrix multiplication. In Proceedings of the \nth\intcalcSub20141968 Annual ACM Symposium on Theory of Computing (STOC 2014), pages 128-135, 2014. URL: http://dx.doi.org/10.1145/2591796.2591824.
  26. Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil P. Vadhan. Better pseudorandom generators from milder pseudorandom restrictions. In Proceedings of the \ifnumcomp2012<1966\nth\intcalcSub20121959 Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 2012)\ifnumcomp2012<1975\nth\intcalcSub20121959 Annual Symposium on Switching and Automata Theory (SWAT 2012)\nth\intcalcSub20121959 Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012), pages 120-129. IEEE Computer Society, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.77.
  27. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Arithmetic Circuits: A Chasm at Depth Three. In Proceedings of the \ifnumcomp2013<1966\nth\intcalcSub20131959 Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 2013)\ifnumcomp2013<1975\nth\intcalcSub20131959 Annual Symposium on Switching and Automata Theory (SWAT 2013)\nth\intcalcSub20131959 Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), pages 578-587, 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.68.
  28. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Approaching the chasm at depth four. Journal of the ACM, 61(6):33:1-33:16, 2014. Preliminary version in the \ifnumcomp2013<1996\nth\intcalcSub20131985 Annual Structure in Complexity Theory Conference (Structures 2013)\ifnumcomp2013<2015\nth\intcalcSub20131985 Annual IEEE Conference on Computational Complexity (CCC 2013)\nth\intcalcSub20131985 Annual Computational Complexity Conference (CCC 2013). URL: http://dx.doi.org/10.1145/2629541.
  29. Rohit Gurjar, Arpita Korwar, Nitin Saxena, and Thomas Thierauf. Deterministic identity testing for sum of read-once oblivious arithmetic branching programs. In Proceedings of the \ifnumcomp2015<1996\nth\intcalcSub20151985 Annual Structure in Complexity Theory Conference (Structures 2015)\ifnumcomp2015<2015\nth\intcalcSub20151985 Annual IEEE Conference on Computational Complexity (CCC 2015)\nth\intcalcSub20151985 Annual Computational Complexity Conference (CCC 2015), pages 323-346, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2015.323.
  30. Joos Heintz and Claus-Peter Schnorr. Testing Polynomials which Are Easy to Compute (Extended Abstract). In Proceedings of the \nth\intcalcSub19801968 Annual ACM Symposium on Theory of Computing (STOC 1980), pages 262-272, 1980. URL: http://dx.doi.org/10.1145/800141.804674.
  31. Russell Impagliazzo, Raghu Meka, and David Zuckerman. Pseudorandomness from shrinkage. In Proceedings of the \ifnumcomp2012<1966\nth\intcalcSub20121959 Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 2012)\ifnumcomp2012<1975\nth\intcalcSub20121959 Annual Symposium on Switching and Automata Theory (SWAT 2012)\nth\intcalcSub20121959 Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012), pages 111-119, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.78.
  32. Russell Impagliazzo, Noam Nisan, and Avi Wigderson. Pseudorandomness for network algorithms. In Proceedings of the \nth\intcalcSub19941968 Annual ACM Symposium on Theory of Computing (STOC 1994), pages 356-364, 1994. URL: http://dx.doi.org/10.1145/195058.195190.
  33. Maurice J. Jansen, Youming Qiao, and Jayalal Sarma. Deterministic identity testing of read-once algebraic branching programs. Electronic Colloquium on Computational Complexity (ECCC), 17:84, 2010. URL: http://eccc.hpi-web.de/report/2010/084.
  34. 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 \nth\intcalcSub20031968 Annual ACM Symposium on Theory of Computing (STOC 2003). URL: http://dx.doi.org/10.1007/s00037-004-0182-6.
  35. Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, and Ilya Volkovich. Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in. SIAM Journal of Computing, 42(6):2114-2131, 2013. Preliminary version in the \nth\intcalcSub20101968 Annual ACM Symposium on Theory of Computing (STOC 2010). URL: http://dx.doi.org/10.1137/110824516.
  36. 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 \nth\intcalcSub19851968 Annual ACM Symposium on Theory of Computing (STOC 1985). URL: http://dx.doi.org/10.1007/BF02579407.
  37. Neeraj Kayal, Nutan Limaye, Chandan Saha, and Srikanth Srinivasan. An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Circuits. In Proceedings of the \ifnumcomp2014<1966\nth\intcalcSub20141959 Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 2014)\ifnumcomp2014<1975\nth\intcalcSub20141959 Annual Symposium on Switching and Automata Theory (SWAT 2014)\nth\intcalcSub20141959 Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014), 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.15.
  38. Neeraj Kayal, Vineet Nair, and Chandan Saha. Separation between read-once oblivious algebraic branching programs (roabps) and multilinear depth three circuits. Electronic Colloquium on Computational Complexity (ECCC), 22:154, 2015. URL: http://eccc.hpi-web.de/report/2015/154/.
  39. Neeraj Kayal, Chandan Saha, and Ramprasad Saptharishi. A super-polynomial lower bound for regular arithmetic formulas. In Proceedings of the \nth\intcalcSub20141968 Annual ACM Symposium on Theory of Computing (STOC 2014), pages 146-153, 2014. URL: http://dx.doi.org/10.1145/2591796.2591847.
  40. Neeraj Kayal and Shubhangi Saraf. Blackbox polynomial identity testing for depth-3 circuits. In Proceedings of the \ifnumcomp2009<1966\nth\intcalcSub20091959 Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 2009)\ifnumcomp2009<1975\nth\intcalcSub20091959 Annual Symposium on Switching and Automata Theory (SWAT 2009)\nth\intcalcSub20091959 Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), 2009. URL: http://dx.doi.org/10.1109/FOCS.2009.67.
  41. Neeraj Kayal and Nitin Saxena. Polynomial identity testing for depth 3 circuits. Computational Complexity, 16(2):115-138, 2007. URL: http://dx.doi.org/10.1007/s00037-007-0226-9.
  42. Pascal Koiran. Arithmetic circuits: The chasm at depth four gets wider. Theoretical Computer Science, 448:56-65, 2012. URL: http://dx.doi.org/10.1016/j.tcs.2012.03.041.
  43. Swastik Kopparty, Shubhangi Saraf, and Amir Shpilka. Equivalence of polynomial identity testing and polynomial factorization. Computational Complexity, 24(2):295-331, 2015. Preliminary version in the \ifnumcomp2014<1996\nth\intcalcSub20141985 Annual Structure in Complexity Theory Conference (Structures 2014)\ifnumcomp2014<2015\nth\intcalcSub20141985 Annual IEEE Conference on Computational Complexity (CCC 2014)\nth\intcalcSub20141985 Annual Computational Complexity Conference (CCC 2014). URL: http://dx.doi.org/10.1007/s00037-015-0102-y.
  44. Michal Koucký, Prajakta Nimbhorkar, and Pavel Pudlák. Pseudorandom generators for group products: extended abstract. In Proceedings of the \nth\intcalcSub20111968 Annual ACM Symposium on Theory of Computing (STOC 2011), pages 263-272, 2011. URL: http://dx.doi.org/10.1145/1993636.1993672.
  45. Joseph B Kruskal. Monotonic subsequences. Proceedings of the American Mathematical Society, 4(2):264-274, 1953. URL: http://dx.doi.org/10.1090/S0002-9939-1953-0053256-2.
  46. Mrinal Kumar and Shubhangi Saraf. The limits of depth reduction for arithmetic formulas: it’s all about the top fan-in. In Proceedings of the \nth\intcalcSub20141968 Annual ACM Symposium on Theory of Computing (STOC 2014), pages 136-145, 2014. URL: http://dx.doi.org/10.1145/2591796.2591827.
  47. Mrinal Kumar and Shubhangi Saraf. On the power of homogeneous depth 4 arithmetic circuits. In Proceedings of the \ifnumcomp2014<1966\nth\intcalcSub20141959 Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 2014)\ifnumcomp2014<1975\nth\intcalcSub20141959 Annual Symposium on Switching and Automata Theory (SWAT 2014)\nth\intcalcSub20141959 Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014), 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.46.
  48. Ketan Mulmuley. Geometric complexity theory V: equivalence between blackbox derandomization of polynomial identity testing and derandomization of noether’s normalization lemma. In Proceedings of the \ifnumcomp2012<1966\nth\intcalcSub20121959 Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 2012)\ifnumcomp2012<1975\nth\intcalcSub20121959 Annual Symposium on Switching and Automata Theory (SWAT 2012)\nth\intcalcSub20121959 Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012), pages 629-638, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.15.
  49. 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 \nth\intcalcSub19871968 Annual ACM Symposium on Theory of Computing (STOC 1987). URL: http://dx.doi.org/10.1007/BF02579206.
  50. Noam Nisan. Lower bounds for non-commutative computation. In Proceedings of the \nth\intcalcSub19911968 Annual ACM Symposium on Theory of Computing (STOC 1991), pages 410-418, 1991. URL: http://dx.doi.org/10.1145/103418.103462.
  51. Noam Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449-461, 1992. URL: http://dx.doi.org/10.1007/BF01305237.
  52. E.A. Okolnishnikova. Lower bounds on the complexity of realization of characteristic functions of binary codes by branching programs. Metody Diskretnogo Analiza, 51:61-83, 1991. URL: http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/Russians/Okolnishnikova-1991.pdf.
  53. Rafael Oliveira, Amir Shpilka, and Ben Lee Volk. Subexponential size hitting sets for bounded depth multilinear formulas. In Proceedings of the \ifnumcomp2015<1996\nth\intcalcSub20151985 Annual Structure in Complexity Theory Conference (Structures 2015)\ifnumcomp2015<2015\nth\intcalcSub20151985 Annual IEEE Conference on Computational Complexity (CCC 2015)\nth\intcalcSub20151985 Annual Computational Complexity Conference (CCC 2015), pages 304-322, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2015.304.
  54. Ran Raz and Amir Shpilka. Deterministic polynomial identity testing in non-commutative models. Computational Complexity, 14(1):1-19, 2005. Preliminary version in the \ifnumcomp2004<1996\nth\intcalcSub20041985 Annual Structure in Complexity Theory Conference (Structures 2004)\ifnumcomp2004<2015\nth\intcalcSub20041985 Annual IEEE Conference on Computational Complexity (CCC 2004)\nth\intcalcSub20041985 Annual Computational Complexity Conference (CCC 2004). URL: http://dx.doi.org/10.1007/s00037-005-0188-8.
  55. Ran Raz and Amir Yehudayoff. Lower bounds and separations for constant depth multilinear circuits. Computational Complexity, 18(2):171-207, 2009. Preliminary version in the \ifnumcomp2008<1996\nth\intcalcSub20081985 Annual Structure in Complexity Theory Conference (Structures 2008)\ifnumcomp2008<2015\nth\intcalcSub20081985 Annual IEEE Conference on Computational Complexity (CCC 2008)\nth\intcalcSub20081985 Annual Computational Complexity Conference (CCC 2008). URL: http://dx.doi.org/10.1007/s00037-009-0270-8.
  56. Omer Reingold, Thomas Steinke, and Salil P. Vadhan. Pseudorandomness for regular branching programs via fourier analysis. In Proceedings of the \nth\intcalcSub20131996 International Workshop on Randomization and Computation (RANDOM 2013), pages 655-670, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40328-6_45.
  57. Shubhangi Saraf and Ilya Volkovich. Black-box identity testing of depth-4 multilinear circuits. In Proceedings of the \nth\intcalcSub20111968 Annual ACM Symposium on Theory of Computing (STOC 2011), pages 421-430, 2011. URL: http://dx.doi.org/10.1145/1993636.1993693.
  58. Nitin Saxena and C. Seshadhri. Blackbox identity testing for bounded top-fanin depth-3 circuits: The field doesn't matter. SIAM J. Comput., 41(5):1285-1298, 2012. Preliminary version in the \nth\intcalcSub20111968 Annual ACM Symposium on Theory of Computing (STOC 2011). URL: http://dx.doi.org/10.1137/10848232.
  59. Jacob T. Schwartz. Fast Probabilistic Algorithms for Verification of Polynomial Identities. Journal of the ACM, 27(4):701-717, 1980. URL: http://dx.doi.org/10.1145/322217.322225.
  60. Amir Shpilka and Ilya Volkovich. On the relation between polynomial identity testing and finding variable disjoint factors. In Proceedings of the \nth\intcalcSub20101973 International Colloquium on Automata, Languages and Programming (ICALP 2010), pages 408-419, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14165-2_35.
  61. Amir Shpilka and Ilya Volkovich. Read-once polynomial identity testing. Computational Complexity, 24(3):477-532, 2015. Preliminary version in the \nth\intcalcSub20081968 Annual ACM Symposium on Theory of Computing (STOC 2008). URL: http://dx.doi.org/10.1007/s00037-015-0105-8.
  62. Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5:207-388, March 2010. URL: http://dx.doi.org/10.1561/0400000039.
  63. Thomas Steinke. Pseudorandomness for permutation branching programs without the group theory. Electronic Colloquium on Computational Complexity (ECCC), 19:83, 2012. URL: http://eccc.hpi-web.de/report/2012/083.
  64. Thomas Steinke, Salil P. Vadhan, and Andrew Wan. Pseudorandomness and fourier growth bounds for width-3 branching programs. In Proceedings of the \nth\intcalcSub20141996 International Workshop on Randomization and Computation (RANDOM 2014), pages 885-899, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.885.
  65. Sébastien Tavenas. Improved bounds for reduction to depth 4 and depth 3. Inf. Comput., 240:2-11, 2015. Preliminary version in the \nth\intcalcSub20131975 Internationl Symposium on the Mathematical Foundations of Computer Science (MFCS 2013). URL: http://dx.doi.org/10.1016/j.ic.2014.09.004.
  66. Jayram S. Thathachar. On separating the read-k-times branching program hierarchy. In Proceedings of the \nth\intcalcSub19981968 Annual ACM Symposium on Theory of Computing (STOC 1998), pages 653-662, 1998. URL: http://dx.doi.org/10.1145/276698.276881.
  67. Leslie G. Valiant, Sven Skyum, S. Berkowitz, and Charles Rackoff. Fast Parallel Computation of Polynomials Using Few Processors. SIAM Journal of Computing, 12(4):641-644, 1983. Preliminary version in the \nth\intcalcSub19811975 Internationl Symposium on the Mathematical Foundations of Computer Science (MFCS 1981). URL: http://dx.doi.org/10.1137/0212043.
  68. Ingo Wegener. On the complexity of branching programs and decision trees for clique functions. J. ACM, 35(2):461-471, 1988. URL: http://dx.doi.org/10.1145/42282.46161.
  69. Stanislav Zák. An exponential lower bound for one-time-only branching programs. In Proceedings of the \nth\intcalcSub19841975 Internationl Symposium on the Mathematical Foundations of Computer Science (MFCS 1984), volume 176 of Lecture Notes in Computer Science, pages 562-566. Springer, 1984. URL: http://dx.doi.org/10.1007/BFb0030340.
  70. 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: http://dx.doi.org/10.1007/3-540-09519-5_73.
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