{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:33:36Z","timestamp":1725514416517},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540725039"},{"type":"electronic","value":"9783540725046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72504-6_11","type":"book-chapter","created":{"date-parts":[[2007,7,22]],"date-time":"2007-07-22T07:36:39Z","timestamp":1185089799000},"page":"128-135","source":"Crossref","is-referenced-by-count":2,"title":["Finding a Duplicate and a Missing Item in a Stream"],"prefix":"10.1007","author":[{"given":"Jun","family":"Tarui","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Ben-Or, M.: A Theorem on Probabilistic Constant Depth Circuits. In: Proc.\u00a0of STOC84, pp. 471\u2013474 (1984)","DOI":"10.1145\/800057.808715"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The Space Complexity of Approximating the Frequency Moments. In: Proc.\u00a0of STOC97, pp. 20\u201329 (1996)","DOI":"10.1145\/237814.237823"},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1016\/0022-0000(86)90027-9","volume":"32","author":"R. Boppana","year":"1986","unstructured":"Boppana, R.: Threshold Functions and Bounded Depth Monotone Circuits. Journal of Computer and System Sciences\u00a032, 222\u2013229 (1986)","journal-title":"Journal of Computer and System Sciences"},{"key":"11_CR4","volume-title":"Handbook of Theoretical Computer Science, vol.\u00a0A","author":"R. Boppana","year":"1990","unstructured":"Boppana, R., Sipser, M.: The Complexity of Finite Functions. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, vol.\u00a0A, MIT Press, Cambridge (1990)"},{"key":"11_CR5","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1137\/0211022","volume":"11","author":"A. Borodin","year":"1982","unstructured":"Borodin, A., Cook, S.: A Time-Space Trade-Off for Sorting on a General Sequential Model of Computation. SIAM Journal on Computing\u00a011, 287\u2013297 (1982)","journal-title":"SIAM Journal on Computing"},{"key":"11_CR6","volume-title":"Computational Limits for Small-Depth Circuits","author":"J. H\u00e5stad","year":"1987","unstructured":"H\u00e5stad, J.: Computational Limits for Small-Depth Circuits. MIT Press, Cambridge (1987)"},{"key":"11_CR7","volume-title":"Communication Complexity","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)"},{"issue":"4","key":"11_CR8","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/0405044","volume":"5","author":"M. Karchmer","year":"1992","unstructured":"Karchmer, M., Wigderson, A.: Monotone Circuits for Connectivity Requires Super-Logarithmic Depth. SIAM Journal on Discrete Mathematics\u00a05(4), 545\u2013557 (1992)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"11_CR9","unstructured":"Muthukrishnan, S.: talk given at the Kyoto Workshop on New Horizons in Computing (March 2005)"},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S.: Data Streams: Algorithms and Applications. Foundations and Trends in Theoretical Computer Science\u00a01(2) (2005), a preliminary version available at http:\/\/www.cs.rutgers.edu\/~muthu","DOI":"10.1561\/0400000002"},{"issue":"4","key":"11_CR11","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/s00493-002-0007-7","volume":"22","author":"A. Razborov","year":"2002","unstructured":"Razborov, A., Wigderson, A., Yao, A.: Read-Once Branching Programs, Rectangular Proofs of the Pigeon-Hole Principle and the Transversal Calculus. Combinatorica\u00a022(4), 555\u2013574 (2002), also in Proc.\u00a0of STOC97, pp. 739\u2013748 (1997)","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72504-6_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T05:38:03Z","timestamp":1619501883000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72504-6_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540725039","9783540725046"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72504-6_11","relation":{},"subject":[]}}