{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T15:06:26Z","timestamp":1778166386295,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540083535","type":"print"},{"value":"9783540372851","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1977]]},"DOI":"10.1007\/3-540-08353-7_135","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T16:23:48Z","timestamp":1330187028000},"page":"162-176","source":"Crossref","is-referenced-by-count":128,"title":["Graph-theoretic arguments in low-level complexity"],"prefix":"10.1007","author":[{"given":"Leslie G.","family":"Valiant","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,24]]},"reference":[{"key":"13_CR1","unstructured":"Aho, A.V., Hopcroft, J.E. and Ullman, J.D., The Design and Analysis of Computer Algorithms, Addison Wesley, 1974."},{"key":"13_CR2","volume-title":"Mathematical Theory of Connecting Networks and Telephone Traffic","author":"V. E. Bene\u0161","year":"1965","unstructured":"Bene\u0161, V.E., Mathematical Theory of Connecting Networks and Telephone Traffic. Academic Press, New York, 1965."},{"key":"13_CR3","unstructured":"Borodin, A.B. and Munro, I. The Complexity of Algebraic and Numeric Problems, American Elsevier, 1975."},{"key":"13_CR4","unstructured":"Ehrenfeucht, A. Practical decidability. Report CU-CS-008-72, Univ. of Colorado (1972)."},{"key":"13_CR5","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0898-1221(75)90037-1","volume":"1","author":"P. Erd\u00f6s","year":"1975","unstructured":"Erd\u00f6s, P., Graham and Szemer\u00e9di, \u011a. On sparse graphs with dense long paths. Comp. and Maths. with Appls., 1, (1975) 365\u2013369.","journal-title":"Comp. and Maths. with Appls."},{"key":"13_CR6","volume-title":"Super-exponential complexity of Presburger arithmetic","author":"M. J. Fischer","year":"1974","unstructured":"Fischer, M.J. and Rabin, M.O. Super-exponential complexity of Presburger arithmetic. MACTR43, Project MAC, MIT, (1974)."},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.E., Paul, W.J. and Valiant, L.G. Time versus space and related problems. Proc. 16th Symp. on Foundations of Computer Science, Berkeley, (1975) 57\u201364.","DOI":"10.1109\/SFCS.1975.23"},{"key":"13_CR8","unstructured":"Hartmanis, J., Lewis, P.M. and Stearns, R.E. Classification of Computations by time and memory requirements. Proc. IFIP Congress 1965, Spartan, N.Y., 31\u201335."},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"Hyafil, L. and Kung, H.T. The complexity of parallel evaluation of linear recurrence. Proc. 7th ACM Symp. on Theory of Computing (1975) 12\u201322.","DOI":"10.1145\/800116.803748"},{"issue":"4","key":"13_CR10","first-page":"71","volume":"9","author":"G. A. Margulis","year":"1973","unstructured":"Margulis, G.A. Explicit constructions of Concentrators, Problemy Peredachi Informatsii, 9: 4(1973) 71\u201380.","journal-title":"Problemy Peredachi Informatsii"},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Meyer, A.R. and Stockmeyer, L.J. The word problem for regular expressions with squaring requires exponential space. Proc. 13th IEEE Symp. on Switching and Automata Theory, (1972)125\u2013129.","DOI":"10.1109\/SWAT.1972.29"},{"key":"13_CR12","first-page":"97","volume":"7","author":"M. S. Paterson","year":"1974","unstructured":"Paterson, M.S., Fischer, M.J. and Meyer A.R. An improved overlap argument for on-line multiplication. SIAM-AMS Proceedings Vol 7, (1974) 97\u2013111","journal-title":"SIAM-AMS Proceedings"},{"key":"13_CR13","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1016\/0304-3975(76)90090-6","volume":"2","author":"M. S. Paterson","year":"1976","unstructured":"Paterson, M.S. and Valiant, L.G. Circuit size is nonlinear in depth. Theoretical Computer Science 2 (1976) 397\u2013400.","journal-title":"Theoretical Computer Science"},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"Paul, W.J. A 2.5N Lower bound for the combinational complexity of boolean functions. Proc. 7th ACM Symp. on Theory of Computing, (1975) 27\u201336.","DOI":"10.1145\/800116.803750"},{"key":"13_CR15","doi-asserted-by":"crossref","unstructured":"Paul, W.J., Tarjan, R.E. and Celoni, J.R. Space bounds for a game on graphs. Proc. 8th ACM Symp. on Theory of Computing, (1976) 149\u2013160.","DOI":"10.1145\/800113.803643"},{"key":"13_CR16","volume-title":"The complexity theory of switching networks","author":"N. Pippenger","year":"1973","unstructured":"Pippenger, N. The complexity theory of switching networks. Ph.D. Thesis, Dept. of Elect. Eng., MIT, (1973)."},{"key":"13_CR17","unstructured":"Pippenger, N. Superconcentrators. RC5937. IBM Yorktown Heights (1976)."},{"key":"13_CR18","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1145\/321958.321962","volume":"23","author":"N. Pippenger","year":"1976","unstructured":"Pippenger, N. and Valiant, L.G. Shifting graphs and their applications. JACM 23 (1976) 423\u2013432.","journal-title":"JACM"},{"key":"13_CR19","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/BF02246615","volume":"13","author":"C. P. Schnorr","year":"1974","unstructured":"Schnorr, C.P. Zwei lineare Schranken fur die Komplexit\u00e4t Boolischer Funktionen, Computing, 13 (1974) 155\u2013171.","journal-title":"Computing"},{"key":"13_CR20","unstructured":"Stockmeyer, L.J. and Meyer, A.R. Inherent computational complexity of decision problems in logic and automata theory. Lecture Notes in Computer Science (to appear), Springer"},{"key":"13_CR21","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/BF01436566","volume":"20","author":"V. Strassen","year":"1973","unstructured":"Strassen, V. Die Berechnungkomplexit\u00e4t von elementar symmetrichen Funktionen und von Interpolationskoeffizienten. Numer. Math 20 (1973) 238\u2013251.","journal-title":"Numer. Math"},{"key":"13_CR22","first-page":"184","volume":"264","author":"V. Strassen","year":"1973","unstructured":"Strassen, V. Vermeidung von Divisionen, J.Reine Angew.Math., 264, (1973), 184\u2013202.","journal-title":"J.Reine Angew.Math."},{"key":"13_CR23","doi-asserted-by":"crossref","unstructured":"Valiant, L.G. On non-linear lower bounds in computational complexity. Proc. 7th ACM Symp. on Theory of Computing, (1975) 45\u201353.","DOI":"10.1145\/800116.803752"},{"key":"13_CR24","doi-asserted-by":"crossref","unstructured":"Valiant, L.G. Universal circuits. Proc. 8th ACM Symp. on Theory of Computing, (1976) 196\u2013203.","DOI":"10.1145\/800113.803649"},{"key":"13_CR25","volume-title":"Some conjectures relating to superlinear lower bounds","author":"L. G. Valiant","year":"1976","unstructured":"Valiant, L.G. Some conjectures relating to superlinear lower bounds. TR85, Dept. of Comp. Sci., Univ. of Leeds (1976)."},{"key":"13_CR26","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1002\/cpa.3160230204","volume":"23","author":"S. Winograd","year":"1970","unstructured":"Winograd, S. On the number of multiplications necessary to compute certain functions. Comm. on Pure and App. Math. 23 (1970) 165\u2013179.","journal-title":"Comm. on Pure and App. Math."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1977"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-08353-7_135.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T20:00:48Z","timestamp":1742587248000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-08353-7_135"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1977]]},"ISBN":["9783540083535","9783540372851"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-08353-7_135","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1977]]}}}