Name
Abstract | ||
|---|---|---|
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 proving lower
bounds on the rigidity of a matrix, a notion that he introduced in that paper. The largest lower bound for an explicitly given
matrix is due to J. Friedman, who 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 that 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 rigidity, hence it may be easier to prove
a lower bound using this notion. Bibliography: 14 titles. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/s10958-006-0119-5 | Journal of Mathematical Sciences |
Keywords | DocType | Volume |
linear code,lower bound | Journal | 134 |
Issue | Citations | PageRank |
5 | 5 | 0.42 |
References | Authors | |
10 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ramamohan Paturi | 1 | 1260 | 92.20 |
| Pavel Pudlák | 2 | 1378 | 134.50 |