{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T12:48:21Z","timestamp":1648990101068},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p> Karchmer, Kushilevitz and Nisan formulated the formula size problem as an integer programming problem called the rectangle bound and introduced a technique called the LP bound, which gives a formula size lower bound by showing a feasible solution of the dual problem of its LP-relaxation. As extensions of the LP bound, we introduce novel general techniques proving formula size lower bounds, named a quasi-additive bound and the Sherali-Adams bound. While the Sherali-Adams bound is potentially strong enough to give a lower bound matching to the rectangle bound, we prove that the quasi-additive bound can surpass the rectangle bound. We also reveal that the quasi-additive bound is potentially strong enough to prove the matching formula size lower bound. <\/jats:p>","DOI":"10.1142\/s0129054113500378","type":"journal-article","created":{"date-parts":[[2014,4,2]],"date-time":"2014-04-02T06:43:49Z","timestamp":1396421029000},"page":"1339-1354","source":"Crossref","is-referenced-by-count":1,"title":["BREAKING THE RECTANGLE BOUND BARRIER AGAINST FORMULA SIZE LOWER BOUNDS"],"prefix":"10.1142","volume":"24","author":[{"given":"KENYA","family":"UENO","sequence":"first","affiliation":[{"name":"The Hakubi Center for Advanced Research, Graduate School of Informatics, Kyoto University, Yoshida Honmachi, Sakyo-ku, Kyoto 606-8501, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2014,4]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.06.006"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581273"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261556"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.02.004"},{"key":"p_6","first-page":"119","volume":"4","author":"Kamiyama N.","year":"2012","journal-title":"Journal of Math-for-Industry"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480192238482"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1137\/0403021"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01405045"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90330-V"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0212-7"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.3.470.16391"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70918-3_13"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1137\/0801013"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)00190-W"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00060-5"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.02.005"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054113500378","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T17:48:59Z","timestamp":1565200139000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054113500378"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12]]},"references-count":18,"journal-issue":{"issue":"08","published-online":{"date-parts":[[2014,4]]},"published-print":{"date-parts":[[2013,12]]}},"alternative-id":["10.1142\/S0129054113500378"],"URL":"https:\/\/doi.org\/10.1142\/s0129054113500378","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,12]]}}}