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

DOI10.1016/S0020-0190(00)00058-2zbMath1338.68117MaRDI QIDQ294768

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 complexitydeterminantmatrix

Mathematics Subject Classification ID

Related Items (5)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved lower bounds on the rigidity of Hadamard matrices
• The Linear Complexity of Computation
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform

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