A note on the use of determinant for proving lower bounds on the size of linear circuits

DOI10.1016/S0020-0190(00)00058-2MaRDI QIDQ294768zbMATH OpenFDO

Authors Pavel Pudlák

Publication date 16 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019000000582?np=y

zbMATH Keywords

computational complexitymatrixdeterminant

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Determinants, permanents, traces, other special matrix functions (15A15)

Recommendations

• scientific article; zbMATH DE number 2187726
• Linear Circuits over $\operatorname{GF}(2)$
• A Lower Bound for the Formula Size of Rational Functions
• Theory and Applications of Models of Computation
• On the Complexity of Matrix Product

Cites work

• scientific article; zbMATH DE number 3532851 (Why is no real title available?)
• scientific article; zbMATH DE number 3597878 (Why is no real title available?)
• scientific article; zbMATH DE number 1261801 (Why is no real title available?)
• scientific article; zbMATH DE number 1263251 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 3342967 (Why is no real title available?)
• Improved lower bounds on the rigidity of Hadamard matrices
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
• The Linear Complexity of Computation

Cited in

(5)

• Lower bounds for matrix factorization
• A super-quadratic lower bound for depth four arithmetic circuits
• Lower bounds for matrix factorization
• Shadows and intersections: Stability and new proofs
• Entropy of operators or why matrix multiplication is hard for depth-two circuits

This page was built for publication: A note on the use of determinant for proving lower bounds on the size of linear circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q294768)