Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Boolean Decision Trees:
TR97-054 | 17th November 1997
Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolay Vereshchagin

Arthur-Merlin Games in Boolean Decision Trees

It is well known that probabilistic boolean decision trees
cannot be much more powerful than deterministic ones (N.~Nisan, SIAM
Journal on Computing, 20(6):999--1007, 1991). Motivated by a question
if randomization can significantly speed up a nondeterministic
computation via a boolean decision tree, we address structural
properties of Arthur-Merlin games ... more >>>

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