{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:40:23Z","timestamp":1742596823940,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":64,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540575689"},{"type":"electronic","value":"9783540482338"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57568-5_251","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:09:49Z","timestamp":1330261789000},"page":"209-220","source":"Crossref","is-referenced-by-count":11,"title":["Time space tradeoffs (getting closer to the barrier?)"],"prefix":"10.1007","author":[{"given":"Allan","family":"Borodin","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"23_CR1","first-page":"269","volume":"43","author":"K. Abrahamson","year":"1991","unstructured":"K. Abrahamson: Time-space tradeoffs for algebraic problems on general sequential machines. JCSS 43, 269\u2013289 (1991)","journal-title":"JCSS"},{"key":"23_CR2","doi-asserted-by":"crossref","unstructured":"K. Abrahamson: A time-space tradeoff for Boolean Matrix multiplication, In Proc. 31st FOCS, 412\u2013419 (1990)","DOI":"10.1109\/FSCS.1990.89561"},{"key":"23_CR3","doi-asserted-by":"crossref","unstructured":"M. Ajtai, L. Babai, P. Hajnal, J. Komlos, P. Pudlak, V. Rodl, E. Szemeredi, Gy. Turan: Two lower bounds for branching programs, In Proc. 18th ACM STOC, 30\u201338, (1986)","DOI":"10.1145\/12130.12134"},{"key":"23_CR4","doi-asserted-by":"crossref","unstructured":"R. Aleliunas, R.M. Karp, R.J. Lipton, L. Lovasz, C. Rackoff: Random walks, universal traversal sequences, and the complexity of maze problems. In Proc. 20th Annual Symposium on Foundations of Computer Science, 1979, 218\u2013223","DOI":"10.1109\/SFCS.1979.34"},{"key":"23_CR5","first-page":"118","volume":"37","author":"N. Alon","year":"1988","unstructured":"N. Alon, W. Maass: Meanders and their applications in lower bounds arguments. JCSS 37, 118\u2013129 (1988)","journal-title":"JCSS"},{"key":"23_CR6","first-page":"153","volume":"35","author":"L. Babai","year":"1987","unstructured":"L. Babai, P. Hajnal, E. Szemeredi, G. Turan: A lower bound for read-once branching program. JCSS 35, 153\u2013162 (1987)","journal-title":"JCSS"},{"key":"23_CR7","first-page":"204","volume":"45","author":"L. Babai","year":"1992","unstructured":"L. Babai, N. Nisan, M. Szegedy: Multiparty protocols, pseudorandom generators for logspace and time-space trade-offs. JCSS 45, 204\u2013232 (1992)","journal-title":"JCSS"},{"key":"23_CR8","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/0304-3975(90)90080-2","volume":"74","author":"L. Babai","year":"1990","unstructured":"L. Babai, P. Pudl\u00e1k, V. R\u00f6dl, E. Szemer\u00e9di, E. Lower bounds to the complexity of symmetric Boolean functions Theoretical Computer Science, vol 74, 313\u2013324 (1990)","journal-title":"Theoretical Computer Science"},{"key":"23_CR9","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1137\/0218018","volume":"18","author":"A. Bar-Noy","year":"1989","unstructured":"A. Bar-Noy, A. Borodin, M. Karchmer, N. Linial, M. Werman: Bounds on universal sequences. SIAM Journal on Computing 18, 268\u2013277 (1989)","journal-title":"SIAM Journal on Computing"},{"key":"23_CR10","doi-asserted-by":"crossref","unstructured":"G. Barnes, J.F. Buss, W.L. Ruzzo, B. Schieber: A sublinear space, polynomial time algorithm for directed s-t connectivity. In Proc. 7th Annual Conference on Structure in Complexity Theory, 1992, 27\u201333","DOI":"10.1109\/SCT.1992.215378"},{"key":"23_CR11","unstructured":"G. Barnes, J. Edmonds: Time-space trade-off lower bounds for directed ST-connectivity on JAGs and stronger models. To appear in Proc. 34th Annual Symposium on Foundations of Computer science, 1993"},{"key":"23_CR12","doi-asserted-by":"crossref","unstructured":"G. Barnes, U. Feige: Short random walks, In ACM STOC93, 728\u2013737 (1993)","DOI":"10.1145\/167088.167275"},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"G. Barnes, W.L. Ruzzo: Deterministic algorithms for undirected s-t connectivity using polynomial time and sublinear space. In Proc. 23rd Annual ACM Symposium on the Theory of Computing, 1991, 43\u201345","DOI":"10.1145\/103418.103430"},{"key":"23_CR14","doi-asserted-by":"crossref","unstructured":"D.A. Barrington: Bounded-width polynomial-size branching programs recognize exactly those languages in NC1, In Proc. 18th ACM STOC, 1986, 1\u20135","DOI":"10.1145\/12130.12131"},{"key":"23_CR15","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1137\/0220017","volume":"20","author":"P. Beame","year":"1991","unstructured":"P. Beame: A general time-space tradeoff for finding unique elments. SIAM Journal on Computing 20, 270\u2013277 (1991)","journal-title":"SIAM Journal on Computing"},{"key":"23_CR16","doi-asserted-by":"crossref","unstructured":"P. Beame, A. Borodin, P. Raghavan, W.L. Ruzzo, M. Tompa: Time-space tradeoffs for undirected graph connectivity. In Proc. 31st Annual Symposium on Foundations of Computer Science, 1990, 429\u2013438","DOI":"10.1109\/FSCS.1990.89563"},{"key":"23_CR17","unstructured":"P. Beame, S. Cook: unpublished manusrcipt"},{"key":"23_CR18","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1137\/0221006","volume":"21","author":"M. Ben-Or","year":"1992","unstructured":"M. Ben-Or, R. Cleve: Computing Algebraic Formulas Using a Constant Number of Registers, In SIAM Journal on Computing 21, 54\u201358, (1992)","journal-title":"SIAM Journal on Computing"},{"key":"23_CR19","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1137\/0211022","volume":"11","author":"A. Borodin","year":"1982","unstructured":"A. Borodin, S. Cook: A time-space tradeoff for sorting on a general sequential model of computation. SIAM Journal on Computing 11, 287\u2013297 (1982)","journal-title":"SIAM Journal on Computing"},{"key":"23_CR20","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1137\/0215040","volume":"15","author":"A. Borodin","year":"1986","unstructured":"A. Borodin. D. Dolev, F. Fich, W. Paul: Bounds for width two branching programs. SIAM Journal on Computing 15, 549\u2013560 (1986)","journal-title":"SIAM Journal on Computing"},{"key":"23_CR21","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1137\/0216007","volume":"16","author":"A. Borodin","year":"1987","unstructured":"A. Borodin. F. Fich, F. Meyer auf der Heide, E. Upfal, A. Wigderson: A time-space tradeoff for element distinctness. SIAM Journal on Computing 16, 97\u201399 (1987)","journal-title":"SIAM Journal on Computing"},{"key":"23_CR22","first-page":"351","volume":"22","author":"A. Borodin","year":"1979","unstructured":"A. Borodin, M.J. Fischer, D.G. Kirkpatrick, N.A. Lynch, M. Tompa: A time-space tradeoff for sorting on non-oblivious machines. JCSS 22, 351\u2013364 (1979)","journal-title":"JCSS"},{"key":"23_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01200404","volume":"3","author":"A. Borodin","year":"1993","unstructured":"A. Borodin, A. Razborov, R. Smolensky: On lower bounds for read-k times branching programs. Computational Complexity 3, 1\u201318 (1993)","journal-title":"Computational Complexity"},{"key":"23_CR24","first-page":"180","volume":"45","author":"A. Borodin","year":"1992","unstructured":"A. Borodin, W.L. Ruzzo, M. Tompa: Lower bounds on the length of universal traversal sequences. JCSS 45, 180\u2013203 (1992)","journal-title":"JCSS"},{"key":"23_CR25","doi-asserted-by":"crossref","unstructured":"A.Z. Broder, A.R. Karlin, P. Raghavan, E. Upfal: Trading space for time in undirected s-t connectivity. In Proc. 21st Annual ACM Symposium on the Theory of Computing, 1989, 543\u2013549","DOI":"10.1145\/73007.73059"},{"key":"23_CR26","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0304-3975(80)90036-5","volume":"11","author":"A.R. Bruss","year":"1980","unstructured":"A.R. Bruss, A.R. Meyer: On time-space classes and their relation to the theory of real addition. Theoretical Computer Science 11, 59\u201369 (1980)","journal-title":"Theoretical Computer Science"},{"key":"23_CR27","doi-asserted-by":"crossref","unstructured":"A. Chandra, M. Furst, R. Lipton: Multiparty protocols, In Proc. 15th ACM STOC, 94\u201399 (1983)","DOI":"10.1145\/800061.808737"},{"key":"23_CR28","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/BF01200059","volume":"1","author":"R. Cleve","year":"1991","unstructured":"R. Cleve: Towards Optimal Simulations of Formulas by Bounded-Width Programs, Computational Complexity 1, 91\u2013105, (1991)","journal-title":"Computational Complexity"},{"key":"23_CR29","doi-asserted-by":"crossref","unstructured":"A. Cobham: The Recognition problem for the set of perfect squares. IBM Watson Research Center, Research paper RC-1704 (1966)","DOI":"10.1109\/SWAT.1966.30"},{"key":"23_CR30","doi-asserted-by":"publisher","first-page":"636","DOI":"10.1137\/0209048","volume":"9","author":"S.A. Cook","year":"1980","unstructured":"S.A. Cook, C.W. Rackoff: Space lower bounds for maze threadability on restricted machines. SIAM Journal on Computing 9, 636\u2013652 (1980)","journal-title":"SIAM Journal on Computing"},{"key":"23_CR31","doi-asserted-by":"crossref","unstructured":"P. Duris, Z. Galil: A time-space tradeoff for language recognition. In Proc. 22nd Annual Symposium on Foundations of Computer Science, 1981, 53\u201357","DOI":"10.1109\/SFCS.1981.9"},{"key":"23_CR32","unstructured":"J. Edmonds: Time-space lower bounds for undirected and directed ST-connectivity on JAG models. Ph.D. thesis, University of Toronto, 1993"},{"key":"23_CR33","doi-asserted-by":"crossref","unstructured":"J. Edmonds: Time-space trade-offs for undirected st-connectivity on a JAG. In Proc. 25th Annual ACM Symposium on the Theory of Computing, 1993, 718\u2013727","DOI":"10.1145\/167088.167272"},{"key":"23_CR34","unstructured":"U. Feige: A randomized time-space tradoff of 0(mR) for USTCON: To appear in FOCS 93"},{"key":"23_CR35","unstructured":"D. Grigoriev: An Application of separability and independence notions for proving lower bounds of circuit complexity. Notes of Scientific Seminars, 60, Leningrad Department, Steklov Mathematical Institute, 1976, 38\u201348 (in Russian)"},{"issue":"number2","key":"23_CR36","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1145\/322003.322015","volume":"24","author":"J.E. Hopcroft","year":"1977","unstructured":"J.E. Hopcroft, W.J. Paul, L.G. Valiant: On time versus space and related problems, JACM vol 24, number 2, 332\u2013337 (1977)","journal-title":"JACM"},{"key":"23_CR37","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"N. Immerman: Nonderterministic space is closed under complementation. SIAM Journal on Computing 17, 935\u2013938 (1988)","journal-title":"SIAM Journal on Computing"},{"key":"23_CR38","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BF01048274","volume":"2","author":"J.D. Kahn","year":"1989","unstructured":"J.D. Kahn, N. Linial, N. Nisan, M.E. Saks: On the cover time of random walks on graphs. Journal of Theoretical Probability 2, 121\u2013128 (1989)","journal-title":"Journal of Theoretical Probability"},{"key":"23_CR39","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(86)90150-7","volume":"47","author":"M. Karchmer","year":"1986","unstructured":"M. Karchmer: Two time-space tradeoffs for element distinctness. Theoretical Computer Science 47, 237\u2013246 (1986)","journal-title":"Theoretical Computer Science"},{"key":"23_CR40","doi-asserted-by":"crossref","unstructured":"S.R. Kosaraju: Parallel Evaluation of Division-Free Arithmetic Expressions, Proc. of 18th Annual ACM Symp. on Theory of Computing, 1986, pp. 231\u2013239.","DOI":"10.1145\/12130.12153"},{"key":"23_CR41","doi-asserted-by":"crossref","first-page":"985","DOI":"10.1002\/j.1538-7305.1959.tb01585.x","volume":"38","author":"C.Y. Lee","year":"1959","unstructured":"C.Y. Lee: Representation of switching circuits by binary-decision programs. Bell System Technical Journal 38, 985\u2013999 (1959)","journal-title":"Bell System Technical Journal"},{"key":"23_CR42","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1145\/322344.322354","volume":"29","author":"T. Lengauer","year":"1982","unstructured":"T. Lengauer, R.E. Tarjan: Asymptotically tight bounds on time-space trade-offs in a pebble game. JACM 29, 1087\u20131130 (1982)","journal-title":"JACM"},{"key":"23_CR43","doi-asserted-by":"crossref","unstructured":"Y. Mansour, N. Nisan, P. Tiwari: The computational complexity of universal hashing. In Proc. 22nd Annual ACM Symposium on the Theory of Computing, 1990, 235\u2013243","DOI":"10.1145\/100216.100246"},{"key":"23_CR44","volume-title":"M.Sc. thesis","author":"W. Masek","year":"1976","unstructured":"W. Masek: A fast algorithm for the string editing problem and decision graph complexity. M.Sc. thesis, Massachusetts Institute of Technology, Cambridge, 1976"},{"key":"23_CR45","doi-asserted-by":"crossref","unstructured":"N. Nisan: $$RL \\subseteq SC$$ , In Proc. 24th Annual ACM Symposium on the Theory of Computing, 1992, 619\u2013623","DOI":"10.1145\/129712.129772"},{"key":"23_CR46","first-page":"61","volume":"51","author":"E.A. Okolnishnikova","year":"1991","unstructured":"E.A. Okolnishnikova: Lower bounds for branching programs computing characteristic functions of binary codes. Metody Discretnogo Analiza 51, 61\u201383 (1991) (in Russian)","journal-title":"Metody Discretnogo Analiza"},{"key":"23_CR47","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0304-3975(93)90352-T","volume":"110","author":"B. Patt-Shamir","year":"1993","unstructured":"B. Patt-Shamir, D. Pelag: Time-space tradeoffs for Set Operations, Theoretical Computer Science 110, 99\u2013129 (1993)","journal-title":"Theoretical Computer Science"},{"key":"23_CR48","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF00289150","volume":"10","author":"W.J. Paul","year":"1978","unstructured":"W.J. Paul, R.E. Tarjan: Time-space trade-offs in a pebble game. Acta Informatica 10, 111\u2013115 (1978)","journal-title":"Acta Informatica"},{"issue":"number3","key":"23_CR49","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/BF01683275","volume":"10","author":"W.J. Paul","year":"1977","unstructured":"W.J. Paul, R.E. Tarjan, J.R. Celoni Space Bounds for a Game on Graphs, Mathematical Systems Theory, vol 10, number 3, 239\u2013251 (1977) (See also Correction in vol 11,number 1,page 85, 1977)","journal-title":"Mathematical Systems Theory"},{"key":"23_CR50","unstructured":"N. Pippenger: Pebbling. In Proc. 5th IBM Symposium on Mathematical Foundations of Computer Science, 1980"},{"key":"23_CR51","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1145\/322077.322091","volume":"25","author":"N. Pippenger","year":"1978","unstructured":"N. Pippenger: A time-space trade-off, J. ACM 25, 509\u2013515 (1978)","journal-title":"J. ACM"},{"key":"23_CR52","doi-asserted-by":"crossref","unstructured":"C.K. Poon: Space bounds for graph connectivity problems on node-named JAGs and node-ordered JAGs. To appear in Proc. 34th Annual Symposium on Foundations of Computer science, 1993","DOI":"10.1109\/SFCS.1993.366865"},{"key":"23_CR53","series-title":"Lecture Notes in Computer Scienc, 529","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/3-540-54458-5_49","volume-title":"Proc. 8th FCT","author":"A. Razborov","year":"1991","unstructured":"A. Razborov: Lower bounds for deterministic and nondeterministic branching programs. In Proc. 8th FCT, Lecture Notes in Computer Scienc, 529, New York\/Berlin, 1991, Springer-Verlag, 47\u201360"},{"key":"23_CR54","doi-asserted-by":"publisher","first-page":"839","DOI":"10.1145\/322217.322233","volume":"27","author":"R. Reischuk","year":"1980","unstructured":"R. Reischuk: Improved bounds on the problem of time-space trade-off in the pebble game, J. ACM 27, 839\u2013850 (1980)","journal-title":"J. ACM"},{"key":"23_CR55","unstructured":"J.E. Savage: Space-time tradeoffs \u2014 A survey. In Proc. 3rd Hungarian Computer Science Conference, 1981"},{"key":"23_CR56","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1109\/TIT.1978.1055938","volume":"24","author":"J.E. Savage","year":"1978","unstructured":"J.E. Savage, S. Swamy: Space-time tradeoffs on the FFT algorithm. IEEE Trans. Inform. Theory 24, 563\u2013568 (1978)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"23_CR57","first-page":"177","volume":"4","author":"W.J. Savitch","year":"1970","unstructured":"W.J. Savitch: Relationships between nondeterministic and deterministic tape complexities. JCSS 4, 177\u2013192 (1970)","journal-title":"JCSS"},{"key":"23_CR58","unstructured":"J. Shearer: unpublished manuscript"},{"key":"23_CR59","first-page":"96","volume":"33","author":"R. Szelepcs\u00e9nyi","year":"1987","unstructured":"R. Szelepcs\u00e9nyi: The method of forcing for nondeterministic automata. Bulla\u0117uropean Assoc. Theoret. Comput. Sci. 33, 96\u2013100 (1987)","journal-title":"Bulla\u0117uropean Assoc. Theoret. Comput. Sci."},{"key":"23_CR60","first-page":"118","volume":"20","author":"M. Tompa","year":"1980","unstructured":"M. Tompa: Time-space tradeoffs for computing functions, using connectivity properties of their circuits. JCSS 20, 118\u2013132 (1980)","journal-title":"JCSS"},{"issue":"no.1","key":"23_CR61","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1137\/0211010","volume":"11","author":"M. Tompa","year":"1982","unstructured":"M. Tompa: Two Familiar Transitive Closure Algorithms which Admit no Polynomial Time, Sublinear Space Implementations, Siam Journal on Computing vol 11, no. 1, 130\u2013137 (1982)","journal-title":"Siam Journal on Computing"},{"key":"23_CR62","doi-asserted-by":"crossref","unstructured":"A.C. Yao: Near-optimal time-space tradeoff for element distinctness. In Proc. 29th Annual Symposium on Foundations of Computer Science, 1988, 91\u201397. Accepted for publication in Siam Journal on Computing.","DOI":"10.1109\/SFCS.1988.21925"},{"key":"23_CR63","first-page":"183","volume":"29","author":"Y. Yesha","year":"1984","unstructured":"Y. Yesha: Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer. SIAM Journal on Computing 29, 183\u2013197 (1984)","journal-title":"SIAM Journal on Computing"},{"key":"23_CR64","series-title":"Lecture Notes in Computer Science, 176","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1007\/BFb0030340","volume-title":"Proc. 11th MFCT","author":"S. Zak","year":"1984","unstructured":"S. Zak: An exponential lower bound for one-time-only branching programs. In Proc. 11th MFCT, Lecture Notes in Computer Science, 176, New York\/Berlin, 1984, Springer-Verlag, 562\u2013566"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57568-5_251.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:12:17Z","timestamp":1742595137000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57568-5_251"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540575689","9783540482338"],"references-count":64,"URL":"https:\/\/doi.org\/10.1007\/3-540-57568-5_251","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}