All reports by Author Vince Grolmusz:

__
TR03-074
| 24th June 2003
__

Vince Grolmusz#### Sixtors and Mod 6 Computations

__
TR03-058
| 22nd July 2003
__

Vince Grolmusz#### Defying Dimensions Modulo 6

Revisions: 2

__
TR03-001
| 8th January 2003
__

Vince Grolmusz#### Near Quadratic Matrix Multiplication Modulo Composites

Comments: 1

__
TR02-052
| 3rd September 2002
__

Vince Grolmusz#### Computing Elementary Symmetric Polynomials with a Sub-Polynomial Number of Multiplications

Revisions: 1

__
TR98-036
| 11th June 1998
__

Vince Grolmusz, GĂˇbor Tardos#### Lower Bounds for (MOD p -- MOD m) Circuits

__
TR95-046
| 4th August 1995
__

Vince Grolmusz#### On the Power of Circuits with Gates of Low L_1 Norms

Vince Grolmusz

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 >>>

Vince Grolmusz

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.

more >>>Vince Grolmusz

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.

Vince Grolmusz

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 >>>

Vince Grolmusz, GĂˇbor Tardos

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 >>>

Vince Grolmusz

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 >>>