{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,6]],"date-time":"2023-12-06T16:42:42Z","timestamp":1701880962636},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,12,16]],"date-time":"2016-12-16T00:00:00Z","timestamp":1481846400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2017,6]]},"DOI":"10.1007\/s00037-016-0150-y","type":"journal-article","created":{"date-parts":[[2016,12,17]],"date-time":"2016-12-17T04:17:29Z","timestamp":1481948249000},"page":"393-420","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["On Approximating the Eigenvalues of Stochastic Matrices in Probabilistic Logspace"],"prefix":"10.1007","volume":"26","author":[{"given":"Dean","family":"Doron","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amir","family":"Sarid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amnon","family":"Ta-Shma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,12,16]]},"reference":[{"key":"150_CR1","doi-asserted-by":"publisher","unstructured":"Romas Aleliunas, Richard M. Karp, R.J. Lipton, Laszlo Lovasz & C. Rackoff (1979). Random walks, universal traversal sequences, and the complexity of maze problems. In 20th Annual Symposium on Foundations of Computer Science, 218\u2013223.","DOI":"10.1109\/SFCS.1979.34"},{"issue":"2","key":"150_CR2","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/PL00001603","volume":"9","author":"Carme Alvarez","year":"2000","unstructured":"Alvarez Carme, Greenlaw Raymond (2000) A compendium of problems complete for symmetric logarithmic space. Computational Complexity 9(2): 123\u2013145","journal-title":"Computational Complexity"},{"key":"150_CR3","doi-asserted-by":"publisher","unstructured":"Stephen A. Cook (1985). A taxonomy of problems with fast parallel algorithms. Information and Control 64(13). International Conference on Foundations of Computation Theory.","DOI":"10.1016\/S0019-9958(85)80041-3"},{"issue":"6","key":"150_CR4","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1137\/0205040","volume":"5","author":"L. Csansky","year":"1976","unstructured":"Csansky L. (1976) Fast parallel matrix inversion algorithms. SIAM Journal of Computing 5(6): 618\u2013623","journal-title":"SIAM Journal of Computing"},{"issue":"8","key":"150_CR5","doi-asserted-by":"publisher","first-page":"3441","DOI":"10.1137\/100783030","volume":"39","author":"Ilias Diakonikolas","year":"2010","unstructured":"Diakonikolas Ilias, Gopalan Parikshit, Jaiswal Ragesh, A Servedio Rocco, Viola Emanuele (2010) Bounded independence fools halfspaces. SIAM Journal on Computing 39(8): 3441\u20133462","journal-title":"SIAM Journal on Computing"},{"key":"150_CR6","doi-asserted-by":"publisher","unstructured":"Dean Doron & Amnon Ta-Shma (2015a). On the de-randomization of space-bounded approximate counting problems. Information Processing Letters 115(10), 750\u2013753","DOI":"10.1016\/j.ipl.2015.03.005"},{"key":"150_CR7","doi-asserted-by":"publisher","unstructured":"Dean Doron & Amnon Ta-Shma (2015b). On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace. In International Colloquium on Automata, Languages, and Programming, 419\u2013431. Springer.","DOI":"10.1007\/978-3-662-47672-7_34"},{"issue":"1","key":"150_CR8","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/s11854-007-0011-3","volume":"101","author":"Alexandre Eremenko","year":"2007","unstructured":"Eremenko Alexandre, Yuditskii Peter (2007) Uniform approximation of sgn(x) by polynomials and entire functions. Journal d\u2019Analyse Math\u00e9matique 101(1): 313\u2013324","journal-title":"Journal d\u2019Analyse Math\u00e9matique"},{"key":"150_CR9","unstructured":"Bill Fefferman & Cedric Yen-Yu Lin (2016). A Complete Characterization of Unitary Quantum Space. \n                        arXiv:1604.01384\n                        \n                    ."},{"key":"150_CR10","doi-asserted-by":"publisher","unstructured":"James Allen Fill (1991). Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process. The Annals of Applied Probability 62\u201387.","DOI":"10.1214\/aoap\/1177005981"},{"key":"150_CR11","doi-asserted-by":"publisher","unstructured":"Aram W. Harrow, Avinatan Hassidim & Seth Lloyd (2009). Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103, 150\u2013502.","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"150_CR12","unstructured":"K. Hoffman (2007). Banach Spaces of Analytic Functions. Dover Books on Mathematics Series. Dover Publications, Incorporated. ISBN 9780486458748."},{"key":"150_CR13","doi-asserted-by":"publisher","unstructured":"Russell Impagliazzo & Avi Wigderson (1997). P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. In Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, STOC \u201997, 220\u2013229. ACM, New York, NY, USA.","DOI":"10.1145\/258533.258590"},{"key":"150_CR14","doi-asserted-by":"publisher","unstructured":"Mark Jerrum, Alistair Sinclair & Eric Vigoda (2004). A Polynomial-time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries. J. ACM 51(4), 671\u2013697. ISSN 0004-5411.","DOI":"10.1145\/1008731.1008738"},{"issue":"5","key":"150_CR15","doi-asserted-by":"publisher","first-page":"1501","DOI":"10.1137\/S0097539700389652","volume":"31","author":"Klivans. Adam R","year":"2002","unstructured":"Adam R Klivans., Dieter van Melkebeek (2002) Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM Journal on Computing 31(5): 1501\u20131526","journal-title":"SIAM Journal on Computing"},{"key":"150_CR16","doi-asserted-by":"publisher","unstructured":"Swastik Kopparty, Shubhangi Saraf & Amir Shpilka (2014). Equivalence of polynomial identity testing and deterministic multivariate polynomial factorization. In 2014 IEEE 29th Conference on Computational Complexity (CCC), 169\u2013180. IEEE.","DOI":"10.1109\/CCC.2014.25"},{"key":"150_CR17","unstructured":"Fran\u00e7ois Le Gall (2016). Solving Laplacian Systems in Logarithmic Space. \n                        arXiv:1608.01426\n                        \n                    ."},{"issue":"2","key":"150_CR18","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0304-3975(82)90058-5","volume":"19","author":"Lewis. Harry R.","year":"1982","unstructured":"Harry R. Lewis., Christos H. Papadimitriou (1982) Symmetric space-bounded computation. Theoretical Computer Science 19(2): 161\u2013187","journal-title":"Theoretical Computer Science"},{"key":"150_CR19","unstructured":"Dieter van Melkebeek & Thomas Watson (2010). Time-Space Efficient Simulations of Quantum Computations. Electronic Colloquium on Computational Complexity (ECCC) 17, 147."},{"key":"150_CR20","doi-asserted-by":"publisher","unstructured":"Milena Mihail (1989). Conductance and convergence of Markov chains-A combinatorial treatment of expanders. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 526\u2013531. IEEE Comput. Soc. Press.","DOI":"10.1109\/SFCS.1989.63529"},{"issue":"4","key":"150_CR21","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/BF01305237","volume":"12","author":"Noam Nisan","year":"1992","unstructured":"Nisan Noam (1992) Pseudorandom generators for space-bounded computation. Combinatorica 12(4): 449\u2013461","journal-title":"Combinatorica"},{"issue":"1","key":"150_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01205052","volume":"4","author":"Noam Nisan","year":"1994","unstructured":"Noam Nisan (1994) RL\n\n$${\\subseteq}$$\n                        \n                            \n                                            \n                                \u2286\n                            \n                        \n                     SC. Computational Complexity 4(1): 1\u201311","journal-title":"Computational Complexity"},{"issue":"2","key":"150_CR23","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"Noam Nisan","year":"1994","unstructured":"Noam Nisan., Avi Wigderson (1994) Hardness vs randomness. Journal of computer and System Sciences 49(2): 149\u2013167","journal-title":"Journal of computer and System Sciences"},{"key":"150_CR24","doi-asserted-by":"publisher","unstructured":"Omer Reingold (2008). Undirected connectivity in log-space. J. ACM 55(4).","DOI":"10.1145\/1391289.1391291"},{"key":"150_CR25","doi-asserted-by":"publisher","unstructured":"Omer Reingold, Luca Trevisan & Salil Vadhan (2006). Pseudorandom walks on regular digraphs and the RL vs. L problem. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, 457\u2013466. ACM.","DOI":"10.1145\/1132516.1132583"},{"key":"150_CR26","unstructured":"Theodore J. Rivlin (1974). The Chebyshev polynomials. Pure and applied mathematics. Wiley. ISBN 9780471724704."},{"key":"150_CR27","doi-asserted-by":"publisher","unstructured":"E. B. Saff & V. Totik (1989). Polynomial Approximation of Piecewise Analytic Functions. Journal of the London Mathematical Society s2-39(3), 487\u2013498.","DOI":"10.1112\/jlms\/s2-39.3.487"},{"key":"150_CR28","doi-asserted-by":"publisher","unstructured":"Michael E. Saks & Shiyu Zhou (1999). \n\n$${BP_{H}SPACE(S)}$$\n                        \n                            \n                                            \n                                \n                                    B\n                                    \n                                        P\n                                        H\n                                    \n                                    S\n                                    P\n                                    A\n                                    C\n                                    E\n                                    \n                                        (\n                                        S\n                                        )\n                                    \n                                \n                            \n                        \n                     \n\n$${\\subseteq}$$\n                        \n                            \n                                            \n                                \u2286\n                            \n                        \n                     \n\n$${DSPACE(S^{3\/2}}$$\n                        \n                            \n                                            \n                                \n                                    D\n                                    S\n                                    P\n                                    A\n                                    C\n                                    E\n                                    (\n                                    \n                                        S\n                                        \n                                            3\n                                            \/\n                                            2\n                                        \n                                    \n                                \n                            \n                        \n                    ). J. Comput. Syst. Sci. 58(2), 376\u2013403","DOI":"10.1006\/jcss.1998.1616"},{"key":"150_CR29","doi-asserted-by":"publisher","unstructured":"Amnon Ta-Shma (2013). Inverting well conditioned matrices in quantum logspace. In Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, STOC \u201913, 881\u2013890. ACM, New York, NY, USA. ISBN 978-1-4503-2029-0.","DOI":"10.1145\/2488608.2488720"},{"key":"150_CR30","unstructured":"A. F. Timan (1963). Theory of Approximation of Functions of a Real Variable. Dover books on advanced mathematics. Pergamon Press. ISBN 9780486678306."},{"issue":"2","key":"150_CR31","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"Valiant Leslie G","year":"1979","unstructured":"Leslie G Valiant (1979) The complexity of computing the permanent. Theoretical computer science 8(2): 189\u2013201","journal-title":"Theoretical computer science"},{"issue":"2","key":"150_CR32","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1006\/jcss.1999.1655","volume":"59","author":"John  Watrous","year":"1999","unstructured":"John Watrous (1999) Space-bounded quantum complexity. Journal of Computer and System Sciences 59(2): 281\u2013326","journal-title":"Journal of Computer and System Sciences"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-016-0150-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0150-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0150-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,5,2]],"date-time":"2017-05-02T13:27:43Z","timestamp":1493731663000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-016-0150-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,16]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,6]]}},"alternative-id":["150"],"URL":"https:\/\/doi.org\/10.1007\/s00037-016-0150-y","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,16]]}}}