Let f : 0 1 n 0 1 be a Boolean function. The certificate complexity C ( f ) is a complexity measure that is quadratically tight for the zero-error randomized query complexity R 0 ( f ) : C ( f ) R 0 ( f ) C ( f ) 2 . In this paper we study a new complexity measure that we call expectational certificate complexity E C ( f ) , which is also a quadratically tight bound on R 0 ( f ) : E C ( f ) R 0 ( f ) = O ( E C ( f ) 2 ) . We prove that E C ( f ) C ( f ) E C ( f ) 2 and show that there is a quadratic separation between the two, thus E C ( f ) gives a tighter upper bound for R 0 ( f ) . The measure is also related to the fractional certificate complexity F C ( f ) as follows: F C ( f ) E C ( f ) = O ( F C ( f ) 3 2 ) . This also connects to an open question by Aaronson whether F C ( f ) is a quadratically tight bound for R 0 ( f ) , as E C ( f ) is in fact a relaxation of F C ( f ) .

In the second part of the work, we upper bound the distributed query complexity D ( f ) for product distributions by the square of the query corruption bound ( cor r ( f ) ) which improves upon a result of Harsha, Jain and Radhakrishnan [2015]. A similar statement for communication complexity is open.