Santhanam (2007) proved that MA/1 does not have circuits of size $n^k$. We translate his result to the heuristic setting by proving that there is a constant $a$ such that for any $k$, there is a language in HeurMA that cannot be solved by circuits of size $n^k$ on more ... more >>>

We introduce strong, and in many cases optimal, lower bounds for the number of queries required to nonadaptively test three fundamental properties of functions $ f : [n]^d \rightarrow \mathbb R$ on the hypergrid: monotonicity, convexity, and the Lipschitz property.
Our lower bounds also apply to the more restricted setting ... more >>>

We obtain a strong direct product theorem for two-party bounded round communication complexity.
Let suc_r(\mu,f,C) denote the maximum success probability of an r-round communication protocol that uses
at most C bits of communication in computing f(x,y) when (x,y)~\mu.
Jain et al. [JPY12] have recently showed that if
more >>>