It is well known that every finite Abelian group $G$ can be
represented as a product of cyclic groups: $G=G_1\times
G_2\times\cdots G_t$, where each $G_i$ is a cyclic group of size
$p^j$ for some prime $p$ and integer $j\ge 1$. If $a_i$ is the
generator of the cyclic group of ... more >>>

In this paper we introduce a variant of pushdown dimension called bounded pushdown (BPD) dimension, that measures the density of information contained in a sequence, relative to a BPD automata, i.e. a finite state machine equipped with an extra infinite memory stack, with the additional requirement that every input symbol ... more >>>

We develop a new technique of proving lower bounds for the randomized communication complexity of boolean functions in the multiparty 'Number on the Forehead' model. Our method is based on the notion of voting polynomial degree of functions and extends the Degree-Discrepancy Lemma in the recent work of Sherstov (STOC'07). ... more >>>