Ran Raz, GĂˇbor Tardos, Oleg Verbitsky, Nikolay Vereshchagin

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

Alexander Razborov, Nikolay Vereshchagin

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