{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T04:49:25Z","timestamp":1725511765212},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540709176"},{"type":"electronic","value":"9783540709183"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70918-3_13","type":"book-chapter","created":{"date-parts":[[2007,5,23]],"date-time":"2007-05-23T23:41:23Z","timestamp":1179963683000},"page":"145-156","source":"Crossref","is-referenced-by-count":4,"title":["A New Rank Technique for Formula Size Lower Bounds"],"prefix":"10.1007","author":[{"given":"Troy","family":"Lee","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"13_CR1","doi-asserted-by":"publisher","first-page":"750","DOI":"10.1006\/jcss.2002.1826","volume":"64","author":"A. Ambainis","year":"2002","unstructured":"Ambainis, A.: Quantum lower bounds by quantum arguments. Journal of Computer and System Sciences\u00a064, 750\u2013767 (2002)","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR2","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1109\/SFCS.2003.1238197","volume-title":"Proceedings of the 44th IEEE Symposium on Foundations of Computer Science","author":"A. Ambainis","year":"2003","unstructured":"Ambainis, A.: Polynomial degree vs. quantum query complexity. In: Proceedings of the 44th IEEE Symposium on Foundations of Computer Science, pp. 230\u2013239. IEEE Computer Society Press, Los Alamitos (2003)"},{"key":"13_CR3","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1109\/CCC.2003.1214419","volume-title":"Proceedings of the 18th IEEE Conference on Computational Complexity","author":"H. Barnum","year":"2003","unstructured":"Barnum, H., Saks, M., Szegedy, M.: Quantum decision trees and semidefinite programming. In: Proceedings of the 18th IEEE Conference on Computational Complexity, pp. 179\u2013193. IEEE Computer Society Press, Los Alamitos (2003)"},{"key":"13_CR4","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1137\/S0097539794261556","volume":"27","author":"J. H\u00e5stad","year":"1998","unstructured":"H\u00e5stad, J.: The shrinkage exponent is 2. SIAM Journal on Computing\u00a027, 48\u201364 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"13_CR5","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/BF01405045","volume":"9","author":"V.M. Khrapchenko","year":"1971","unstructured":"Khrapchenko, V.M.: Complexity of the realization of a linear function in the case of \u03a0-circuits. Math. Notes Acad. Sciences\u00a09, 21\u201323 (1971)","journal-title":"Math. Notes Acad. Sciences"},{"issue":"1","key":"13_CR6","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1137\/S0895480192238482","volume":"8","author":"M. Karchmer","year":"1995","unstructured":"Karchmer, M., Kushilevitz, E., Nisan, N.: Fractional covers and communication complexity. SIAM Journal on Discrete Mathematics\u00a08(1), 76\u201392 (1995)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"13_CR7","volume-title":"Communication Complexity","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)"},{"issue":"2","key":"13_CR8","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1016\/0304-3975(93)90330-V","volume":"116","author":"E. Koutsoupias","year":"1993","unstructured":"Koutsoupias, E.: Improvements on Khrapchenko\u2019s theorem. Theoretical Computer Science\u00a0116(2), 399\u2013403 (1993)","journal-title":"Theoretical Computer Science"},{"key":"13_CR9","first-page":"539","volume-title":"Proceedings of the 20th ACM Symposium on the Theory of Computing","author":"M. Karchmer","year":"1988","unstructured":"Karchmer, M., Wigderson, A.: Monotone connectivity circuits require super-logarithmic depth. In: Proceedings of the 20th ACM Symposium on the Theory of Computing, pp. 539\u2013550. ACM Press, New York (1988)"},{"key":"13_CR10","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s00037-006-0212-7","volume":"15","author":"S. Laplante","year":"2006","unstructured":"Laplante, S., Lee, T., Szegedy, M.: The quantum adversary method and classical formula size lower bounds. Computational Complexity\u00a015, 163\u2013196 (2006)","journal-title":"Computational Complexity"},{"key":"13_CR11","first-page":"330","volume-title":"Proceedings of the 14th ACM Symposium on the Theory of Computing","author":"K. Melhorn","year":"1982","unstructured":"Melhorn, K., Schmidt, E.: Las Vegas is better than determinism in VLSI and distributed computing. In: Proceedings of the 14th ACM Symposium on the Theory of Computing, pp. 330\u2013337. ACM Press, New York (1982)"},{"key":"13_CR12","first-page":"999","volume":"7","author":"E.I. Ne\u010diporuk","year":"1966","unstructured":"Ne\u010diporuk, E.I.: A Boolean function. Soviet Mathematics\u2013Doklady\u00a07, 999\u20131000 (1966)","journal-title":"Soviet Mathematics\u2013Doklady"},{"key":"13_CR13","series-title":"London Mathematical Society Lecture Note Series","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1017\/CBO9780511526633.014","volume-title":"Boolean function complexity","author":"M. Paterson","year":"1992","unstructured":"Paterson, M., Pippenger, N., Zwick, U.: Optimal carry save networks. In: Boolean function complexity. London Mathematical Society Lecture Note Series, vol.\u00a0169, pp. 174\u2013201. Cambridge University Press, Cambridge (1992)"},{"issue":"2","key":"13_CR14","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1006\/jcss.1997.1287","volume":"54","author":"J. Radhakrishnan","year":"1997","unstructured":"Radhakrishnan, J.: Better lower bounds for monotone threshold formulas. Journal of Computer and System Sciences\u00a054(2), 221\u2013226 (1997)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"13_CR15","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02122698","volume":"10","author":"A. Razborov","year":"1990","unstructured":"Razborov, A.: Applications of matrix methods to the theory of lower bounds in computational complexity. Combinatorica\u00a010(1), 81\u201393 (1990)","journal-title":"Combinatorica"},{"key":"13_CR16","series-title":"London Math. Soc. Lecture Notes Series","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1017\/CBO9780511526633.007","volume-title":"Boolean function complexity","author":"A. Razborov","year":"1992","unstructured":"Razborov, A.: On submodular complexity measures. In: Paterson, M. (ed.) Boolean function complexity. London Math. Soc. Lecture Notes Series, vol.\u00a0169, pp. 76\u201383. Cambridge University Press, Cambridge (1992)"},{"key":"13_CR17","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/0196-6774(84)90016-6","volume":"5","author":"L.G. Valiant","year":"1984","unstructured":"Valiant, L.G.: Short monotone formulae for the majority function. Journal of Algorithms\u00a05, 363\u2013366 (1984)","journal-title":"Journal of Algorithms"}],"container-title":["Lecture Notes in Computer Science","STACS 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70918-3_13.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T04:32:07Z","timestamp":1620016327000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70918-3_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540709176","9783540709183"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70918-3_13","relation":{},"subject":[]}}