BREAKING THE RECTANGLE BOUND BARRIER AGAINST FORMULA SIZE LOWER BOUNDS
Kenya Ueno · International Journal of Foundations of Computer Science · 2013
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.