Koiran, Pascal; Nesme, Vincent; Portier, Natacha; Laboratoire de l'informatique du parallélisme
(LIP, 2006-08-30)
(eng) We obtain optimal lower bounds on the nonadaptive probabilistic query complexity
of a class of problems defined by a rather weak symmetry condition. In
fact, for each problem in this class, given a number T of queries ...