Let $f:\{0,1\}^n \rightarrow \{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) \leq R_0(f) \leq C(f)^2$. In this paper we study a new complexity measure that we call expectational certificate complexity $EC(f)$, which is ... more >>>

Valiant (1980) showed that general arithmetic circuits with negation can be exponentially more powerful than monotone ones. We give the first qualitative improvement to this classical result: we construct a family of polynomials $P_n$ in $n$ variables, each of its monomials has positive coefficient, such that $P_n$ can be computed ... more >>>

The notion of lifting theorems is a generic method to lift hardness of one-party functions to two-party lower bounds in communication model. It has many applications in different areas such as proof complexity, game theory, combinatorial optimization. Among many lifting results, a central idea is called Raz-McKenize simulation (FOCS 1997). ... more >>>