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

DOI10.1016/S0020-0190(00)00058-2zbMATH Open1338.68117MaRDI QIDQ294768FDOQ294768

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

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

zbMATH Keywords

computational complexitymatrixdeterminant

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
• Title not available (Why is that?)
• Improved lower bounds on the rigidity of Hadamard matrices
• The Linear Complexity of Computation
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (5)

• A super-quadratic lower bound for depth four arithmetic circuits
• Lower bounds for matrix factorization
• 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)