Elias Koutsoupias
Professor of Computer Science
University of Athens
Panepistimiopolis, Ilissia
Athens 15784

phone: +30 210 7275122
fax: +30 210 7275114

E. Koutsoupias. Improvements on Khrapchenko's theorem. Theoretical Computer Science, 116(2):399--403, August 1993.
Download: pdf ps


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}}

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