文章基本信息

标题：Some structural properties of low rank matrices related to computational complexity
本地全文：下载
作者：Bruno Codenotti ; Pavel Pudlak ; Giovanni Resta 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1997
卷号：1997
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We consider the conjecture stating that a matrix with rank o(n) and ones on the main diagonal must contain nonzero entries on a 22 submatrix with one entry on the main diagonal. We show that a slightly stronger conjecture implies that an explicit linear transformation cannot be computed by linear size and logarithmic depth circuits. We prove some partial results supporting the conjecture.
关键词：Linear Circuits, lower bounds, Matrix Rank, Matrix Rigidity