{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:02:00Z","timestamp":1725562920903},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642151545"},{"type":"electronic","value":"9783642151552"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15155-2_58","type":"book-chapter","created":{"date-parts":[[2010,8,13]],"date-time":"2010-08-13T20:17:45Z","timestamp":1281730665000},"page":"665-676","source":"Crossref","is-referenced-by-count":0,"title":["Breaking the Rectangle Bound Barrier against Formula Size Lower Bounds"],"prefix":"10.1007","author":[{"given":"Kenya","family":"Ueno","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"58_CR1","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.jcss.2005.06.006","volume":"72","author":"A. Ambainis","year":"2006","unstructured":"Ambainis, A.: Polynomial degree vs. quantum query complexity. Journal of Computer and System Sciences\u00a072(2), 220\u2013238 (2006)","journal-title":"Journal of Computer and System Sciences"},{"key":"58_CR2","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01581273","volume":"58","author":"E. Balas","year":"1993","unstructured":"Balas, E., Ceria, S., Cornu\u00e9jols, G.: A lift-and-project cutting plane algorithm for mixed 0\u20131 programs. Mathematical Programming\u00a058, 295\u2013324 (1993)","journal-title":"Mathematical Programming"},{"issue":"1","key":"58_CR3","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 of De\u00a0Morgan formulas is\u00a02. SIAM Journal on Computing\u00a027(1), 48\u201364 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"58_CR4","doi-asserted-by":"crossref","unstructured":"H\u00f8yer, P., Lee, T., \u0160palek, R.: Negative weights make adversaries stronger. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC 2007), pp. 526\u2013535 (2007)","DOI":"10.1145\/1250790.1250867"},{"key":"58_CR5","doi-asserted-by":"publisher","first-page":"1842","DOI":"10.1016\/j.tcs.2010.02.004","volume":"411","author":"P. Hrube\u0161","year":"2010","unstructured":"Hrube\u0161, P., Jukna, S., Kulikov, A., Pudl\u00e1k, P.: On convex complexity measures. Theoretical Computer Science\u00a0411, 1842\u20131854 (2010)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"58_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"},{"issue":"2","key":"58_CR7","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1137\/0403021","volume":"3","author":"M. Karchmer","year":"1990","unstructured":"Karchmer, M., Wigderson, A.: Monotone circuits for connectivity require super-logarithmic depth. SIAM Journal on Discrete Mathematics\u00a03(2), 255\u2013265 (1990)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"58_CR8","doi-asserted-by":"crossref","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 \u03c0-circuits. Mathematical Notes\u00a09, 21\u201323 (1971)","journal-title":"Mathematical Notes"},{"issue":"2","key":"58_CR9","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"},{"issue":"2","key":"58_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(2), 163\u2013196 (2006)","journal-title":"Computational Complexity"},{"issue":"3","key":"58_CR11","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"J.B. Lasserre","year":"2001","unstructured":"Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization\u00a011(3), 796\u2013817 (2001)","journal-title":"SIAM Journal on Optimization"},{"issue":"3","key":"58_CR12","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1287\/moor.28.3.470.16391","volume":"28","author":"M. Laurent","year":"2003","unstructured":"Laurent, M.: A comparison of the Sherali-Adams, Lov\u00e1sz-Schrijver and Lasserre relaxations for 0\u2009\u2212\u20091 programming. Mathematics of Operations Research\u00a028(3), 470\u2013496 (2003)","journal-title":"Mathematics of Operations Research"},{"key":"58_CR13","unstructured":"Lee, T.: Kolmogorov Complexity and Formula Size Lower Bounds. PhD thesis, University of Amsterdam (January 2006)"},{"key":"58_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/978-3-540-70918-3_13","volume-title":"STACS 2007","author":"T. Lee","year":"2007","unstructured":"Lee, T.: A new rank technique for formula size lower bounds. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 145\u2013156. Springer, Heidelberg (2007)"},{"issue":"2","key":"58_CR15","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L. Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM Journal on Optimization\u00a01(2), 166\u2013190 (1991)","journal-title":"SIAM Journal on Optimization"},{"key":"58_CR16","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"H.D. Sherali","year":"1990","unstructured":"Sherali, H.D., Adams, W.P.: A hierarchy of relaxation between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics\u00a03, 411\u2013430 (1990)","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"1","key":"58_CR17","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0166-218X(92)00190-W","volume":"52","author":"H.D. Sherali","year":"1994","unstructured":"Sherali, H.D., Adams, W.P.: A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems. Discrete Applied Mathematics\u00a052(1), 83\u2013106 (1994)","journal-title":"Discrete Applied Mathematics"},{"issue":"1-2","key":"58_CR18","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0166-218X(95)00060-5","volume":"68","author":"H.D. Sherali","year":"1996","unstructured":"Sherali, H.D., Lee, Y.: Tighter representations for set partitioning problems. Discrete Applied Mathematics\u00a068(1-2), 153\u2013167 (1996)","journal-title":"Discrete Applied Mathematics"},{"key":"58_CR19","unstructured":"Spira, P.: On time-hardware complexity tradeoffs for boolean functions. In: Proceedings of the 4th Hawaii Symposium on System Sciences, pp. 525\u2013527 (1971)"},{"key":"58_CR20","unstructured":"Ueno, K.: A stronger LP bound for formula size lower bounds via clique constraints. In: Proceedings of the 26th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2009). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a03, pp. 685\u2013696. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2009)"},{"key":"58_CR21","volume-title":"The Complexity of Boolean Functions","author":"I. Wegner","year":"1987","unstructured":"Wegner, I.: The Complexity of Boolean Functions. Wiley-Teubner, Chichester (1987)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15155-2_58.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:01:50Z","timestamp":1606186910000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15155-2_58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642151545","9783642151552"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15155-2_58","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}