# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

__Mittagsseminar Talk Information__ | |

**Date and Time**: Tuesday, February 24, 2009, 12:15 pm

**Duration**: This information is not available in the database

**Location**: OAT S15/S16/S17

**Speaker**: Kenya Ueno (The Univ. of Tokyo)

## A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints

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.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login