Elias Koutsoupias / Publications

Abstract

We present an improvement of Khrapchenko's theorem which gives lower bounds for the size of Boolean formulae.Our main theorem gives better lower bound than the original Khrapchenko's theorem or at least the same, although we know of no function where it gives an improvement factor larger that two.This lower bound is the largest eigenvalue of a certain matrix associated with the formula. Moreover, we give an approximation of this bound which is easier to compute and is never smaller than the bound given by Khrapchenko's theorem.

@string{tcs = {Theoretical Computer Science}}

@Article{Kou93,
  author =       {E. Koutsoupias},
  title =        {Improvements on {K}hrapchenko's theorem},
  journal =      tcs,
  year =         1993,
  month =        aug,
  volume =       116,
  number =       2,
  pages =        {399--403}
}