It is shown that complexity of implementation of prefix sums of $m$ variables (i.e. functions $x_1 \cdot \ldots\cdot x_i$, $1\le i \le m$) by circuits of depth $\lceil \log_2 m \rceil$ in the case $m=2^n$ is exactly $$3.5\cdot2^n - (8.5+3.5(n \bmod 2))2^{\lfloor n/2\rfloor} + n + 5.$$ As a consequence, ... more >>>

The Parikh automaton model equips a finite automaton with integer registers and imposes a semilinear constraint on the set of their final settings. Here the theory of typed monoids is used to characterize the language classes that arise algebraically. Complexity bounds are derived, such as containment of the unambiguous Parikh ... more >>>

For a multilinear polynomial $p(x_1,...x_n)$, over the reals, the $L1$-influence is defined to be $\sum_{i=1}^n E_x\left[\frac{|p(x)-p(x^i)|}{2} \right]$, where $x^i$ is $x$ with $i$-th bit swapped. If $p$ maps $\{-1,1\}^n$ to $[-1,1]$, we prove that the $L1$-influence of $p$ is upper bounded by a function of its degree (and independent of ... more >>>