ECCC-Report TR04-004https://eccc.weizmann.ac.il/report/2004/004Comments and Revisions published for TR04-004en-usTue, 13 Jan 2004 17:44:08 +0200
Paper TR04-004
| Circuit lower bounds and linear codes |
Ramamohan Paturi,
Pavel Pudlak
https://eccc.weizmann.ac.il/report/2004/004In 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.
Tue, 13 Jan 2004 17:44:08 +0200https://eccc.weizmann.ac.il/report/2004/004