Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DISJUNCTIVE NORMAL FORMS:
Reports tagged with Disjunctive Normal Forms:
TR99-014 | 30th May 1999
Alexander Razborov, Nikolay Vereshchagin

One Property of Cross-Intersecting Families

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 ... more >>>




ISSN 1433-8092 | Imprint