TR99-014 Authors: Alexander Razborov, Nikolay Vereshchagin

Publication: 31st May 1999 11:32

Downloads: 1123

Keywords:

Assume that A, B are finite families of n-element sets.

We prove that there is an element that simultaneously

belongs to at least |A|/2n sets

in A and to at least |B|/2n sets in B. We use this result to prove

that for any inconsistent DNF's F,G with OR of fanin m and ANDs

of fanin n there is a decision tree of depth

(4n ln m + 2) separating F from G.