Geodesic
Circuit lower bounds and linear codes
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part IX, Tome 316 (2004), pp. 188-204 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

In 1977 Valiant proposed a graph theoretical method for proving lower bounds on algebraic circuits with gates computing linear functions [13]. 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 concept 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 [3]. 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. 
@article{ZNSL_2004_316_a9,
     author = {R. Paturi and P. Pudl\'ak},
     title = {Circuit lower bounds and linear codes},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {188--204},
     year = {2004},
     volume = {316},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2004_316_a9/}
}
TY  - JOUR
AU  - R. Paturi
AU  - P. Pudlák
TI  - Circuit lower bounds and linear codes
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2004
SP  - 188
EP  - 204
VL  - 316
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2004_316_a9/
LA  - en
ID  - ZNSL_2004_316_a9
ER  - 
%0 Journal Article
%A R. Paturi
%A P. Pudlák
%T Circuit lower bounds and linear codes
%J Zapiski Nauchnykh Seminarov POMI
%D 2004
%P 188-204
%V 316
%U http://geodesic.mathdoc.fr/item/ZNSL_2004_316_a9/
%G en
%F ZNSL_2004_316_a9
R. Paturi; P. Pudlák. Circuit lower bounds and linear codes. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part IX, Tome 316 (2004), pp. 188-204. http://geodesic.mathdoc.fr/item/ZNSL_2004_316_a9/

[1] M. Alekhnovich, “More on average case vs. approximation complexity”, Proc. of the 44rd IEEE Symposium on Foundations of Computer Science, 2003, 298–307

[2] N. Alon, J. Spencer, P. Erdös, The Probabilistic Method, John Wiley Sons, 1992 | MR | Zbl

[3] J. Friedman, “A note on matrix rigidity”, Combinatorica, 13:2 (1993), 235–239 | DOI | MR | Zbl

[4] A. Garcia, H. Stichtenoth, “A tower of Artin–Schierer extensions of function fields attaining the Drinfeld–Vlăduţ bound”, Invent. Math., 121 (1995), 211–222 | DOI | MR | Zbl

[5] A. Garcia, H. Stichtenoth, “On the asymptotic behavior of some towers of function fields over finite fields”, J. of Number Theory, 61:2 (1996), 248–273 | DOI | MR | Zbl

[6] D. Yu. Grigoriev, “Using the notion of separability and independence for proving lower bounds on circuit complexity”, Notes of the Leningrad branch of the Steklov Institute, 60, 1976, 38–48 | MR

[7] S. V. Lokam, “On the rigidity of Vandermonde matrices”, Theoretical Computer Science, 237:1–2 (2000), 477–483 | DOI | MR | Zbl

[8] D. J. C. MacKay, “Good error-correcting codes based on very sparse matrices”, IEEE Transaction on Information Theory, 45:2 (1999), 399–401 | DOI | MR

[9] R. Meshulam, A. Wigderson, “Expanders from symmetric codes”, Proc. ACM Symposium on Theory of Computing, 2002, 669–677 | MR | Zbl

[10] M. Morgenstern, “Note on a lower bound on the linear complexity of the Fast Fourier Transform”, J. of ACM, 20:2 (1973), 305–306 | DOI | MR | Zbl

[11] A. A. Razborov, S. Rudich, “Natural proofs”, Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994, 204–213

[12] D. A.Spielman, V. Stetmann, M. A. Shokrollahi, “A remark on matrix rigidity”, Information Processing Letters, 64:6 (1997), 283–285 | DOI | MR

[13] L. G. Valiant, “Graph-theoretic arguments in low-level complexity”, Proceedings of the 6th Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, 53, Springer–Verlag, 1977, 162–176 | MR

[14] J. H. van Lint, Introduction to Coding Theory, Springer-Verlag, 1992 | MR