Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR99-014 | 30th May 1999 00:00

One Property of Cross-Intersecting Families

RSS-Feed




TR99-014
Authors: Alexander Razborov, Nikolay Vereshchagin
Publication: 31st May 1999 11:32
Downloads: 2316
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint