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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M. Alekhnovich, “More on average case vs. approximation complexity,” in: Proceedings of the 44rd IEEE Symposium on Foundations of Computer Science (2003), pp. 298–3
N. Alon, J. Spencer, and P. Erdös, The Probabilistic Method, John Wiley & Sons, Inc., New York (1992).
J. Friedman, “A note on matrix rigidity,” Combinatorica, 13, No. 2, 235–239 (199
A. Garcia and H. Stichtenoth, “A tower of Artin—Schierer extensions of function fields attaining the Drinfeld—Vlăduţ bound,” Invent. Math., 121, 211–222 (1995)
A. Garcia and H. Stichtenoth, “On the asymptotic behavior of some towers of function fields over finite fields,” J. Number Theory, 61, No. 2, 248–273 (199
D. Yu. Grigoriev, “Using the notion of separability and independence for proving lower bounds on circuit complexity,” Zap. Nauchn. Semin. LOMI, 60, 38–48 (197
S. V. Lokam, “On the rigidity of Vandermonde matrices,” Theoret. Comput. Sci., 237, No. 1–2, 477–483 (200
D. J. C. MacKay, “Good error-correcting codes based on very sparse matrices,” IEEE Trans. Inform. Theory, 45, No. 2, 399–401 (199
R. Meshulam and A. Wigderson, “Expanders from symmetric codes,” in: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, ACM, New York (2002), pp. 669–
M. Morgenstern, “Note on a lower bound on the linear complexity of the Fast Fourier Transform,” J. ACM, 20, No. 2, 305–306 (197
A. A. Razborov and S. Rudich, “Natural proofs,” J. Comput. System Sci., 55, 24–35 (199
D. A. Spielman, V. Stetmann, and M. A. Shokrollahi, “A remark on matrix rigidity,” Inform. Process. Lett., 64, No. 6, 283–285 (199
L. G. Valiant, “Graph-theoretic arguments in low-level complexity,” in: Proceedings of the 6th Symposium on Mathematical Foundations of Computer Science, Springer (1977), pp. 162–1
J. H. van Lint, Introduction to Coding Theory, Springer-Verlag, Berlin (1992).
Author information
Authors and Affiliations
Additional information
Published in Zapiski Nauchnykh Seminarov POMI, Vol. 316, 2004, pp. 188–204.
Rights and permissions
About this article
Cite this article
Paturi, R., Pudlák, P. Circuit lower bounds and linear codes. J Math Sci 134, 2425–2434 (2006). https://doi.org/10.1007/s10958-006-0119-5
Received:
Issue Date:
DOI: https://doi.org/10.1007/s10958-006-0119-5