TR04-004 Authors: Ramamohan Paturi, Pavel Pudlak

Publication: 13th January 2004 17:44

Downloads: 1746

Keywords:

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.