Application of separability and independence notions for proving lower bounds of circuit complexity

DOI10.1007/BF01693976zbMath0449.94030OpenAlexW2119106791MaRDI QIDQ1147680

Dima Yu. Grigoriev

Publication date: 1980

Published in: Journal of Soviet Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01693976

zbMATH Keywords

Boolean functionscombinational circuitalgebraic complexity of linear formslower bounds of circuit complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (5)

Parameterized low-rank binary matrix approximation ⋮ Parameterized Low-Rank Binary Matrix Approximation ⋮ Time-space tradeoffs in algebraic complexity theory ⋮ Matrix Rigidity from the Viewpoint of Parameterized Complexity ⋮ Lower bounds in algebraic computational complexity

Cites Work

• Berechnung und Programm. I
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
• Unnamed Item
• Unnamed Item

This page was built for publication: Application of separability and independence notions for proving lower bounds of circuit complexity