  In this work we introduce, both for classical communication complexity and
query complexity, a modification of the 'partition bound' introduced by Jain
and Klauck [2010]. We call it the 'public-coin partition bound'. We show that
(the logarithm to the base two of) its communication complexity and query
complexity versions form, for all relations, a quadratically tight lower bound
on the public-coin randomized communication complexity and randomized query
complexity respectively.
