ECCC-Report TR99-014https://eccc.weizmann.ac.il/report/1999/014Comments and Revisions published for TR99-014en-usMon, 31 May 1999 11:32:14 +0300
Paper TR99-014
| One Property of Cross-Intersecting Families |
Alexander Razborov,
Nikolay Vereshchagin
https://eccc.weizmann.ac.il/report/1999/014Assume 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.
Mon, 31 May 1999 11:32:14 +0300https://eccc.weizmann.ac.il/report/1999/014