We consider the following phenomenon: with just one multiplication
we can compute (3u+2v)(3x+2y)= 3ux+4vy mod 6, while computing the same polynomial modulo 5 needs 2 multiplications. We generalize this observation and we define some vectors, called sixtors, with remarkable zero-divisor properties. Using sixtors, we also generalize our earlier result ... more >>>

We show that a certain representation of the matrix-product can be computed with $n^{o(1)}$ multiplications. We also show, that similar representations of matrices can be compressed enormously with the help of simple linear transforms.

We show how one can use non-prime-power, composite moduli for
computing representations of the product of two $n\times n$ matrices
using only $n^{2+o(1)}$ multiplications.

Elementary symmetric polynomials $S_n^k$ are used as a
benchmark for the bounded-depth arithmetic circuit model of computation.
In this work we prove that $S_n^k$ modulo composite numbers $m=p_1p_2$
can be computed with much fewer multiplications than over any field, if
the coefficients of monomials $x_{i_1}x_{i_2}\cdots x_{i_k}$ ... more >>>

Modular gates are known to be immune for the random
restriction techniques of Ajtai; Furst, Saxe, Sipser; and Yao and
Hastad. We demonstrate here a random clustering technique which
overcomes this difficulty and is capable to prove generalizations of
several known modular circuit lower bounds of Barrington, Straubing,
Therien; Krause ... more >>>

We examine the power of Boolean functions with low L_1 norms in several
settings. In large part of the recent literature, the degree of a polynomial
which represents a Boolean function in some way was chosen to be the measure of the complexity of the Boolean function.
However, some functions ... more >>>