Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR04-004 | 13th January 2004 00:00

Circuit lower bounds and linear codes


Authors: Ramamohan Paturi, Pavel Pudlak
Publication: 13th January 2004 17:44
Downloads: 1714


In 1977 Valiant proposed a graph theoretical method for proving lower
bounds on algebraic circuits with gates computing linear functions.
He used this method to reduce the problem of proving
lower bounds on circuits with linear gates to to proving lower bounds
on the rigidity of a matrix, a concept that he introduced in that
paper. In 1990 J. Friedman proved a lower bound on the rigidity of
the generator matrices of error correcting codes over finite
fields. He showed that the proof can be interpreted as
a bound on a certain parameter defined for all linear spaces of finite
dimension. In this note we define another parameter which can be used
to prove lower bounds on circuits with linear gates. Our parameter may
be larger than Friedman's and it seems incomparable with the rigidity,
hence it may be easier to prove a lower bound using this concept.

ISSN 1433-8092 | Imprint