Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, February 24, 2009, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Kenya Ueno (The Univ. of Tokyo)
A formula is a binary tree with leaves labeled by literals and internal nodes labeled by AND and OR. Formula size is defined as the number of leaves. Proving formula size lower bounds is a fundamental problem in complexity theory. Karchmer, Kushilevitz and Nisan [SIAM J.DM95] formulate the formula size problem as an integer programming problem and devise a technique called the LP bound.
It shows a lower bound by giving a feasible solution for the dual problem of the LP-relaxation. At the same time, they also showed that it cannot prove a lower bound larger than 4n^2. Recently, Laplante, Lee and Szegedy [CCC05] and Lee [STACS07] have shown that the LP bound subsumes several known techniques proving formula size lower bounds.
In this study, we devise a stronger version of the LP bound by utilizing the theory of stable set polytope, especially clique constraints. It tightens the integrality gap which causes the limit of the original technique. To show the relative strength, we apply it to some families of Boolean functions.
Automatic MiSe System Software Version 1.4803M | admin login