Linear Circuits over $\operatorname{GF}(2)$

DOI10.1137/0219074zbMath0712.05015OpenAlexW1514412042MaRDI QIDQ3496345

Noga Alon, Avi Wigderson, Mauricio Karchmer

Publication date: 1990

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0219074

zbMATH Keywords

Hadamard matrixBoolean circuitslinear circuitsgraph coversSize-depth trade-offs

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Combinatorics in computer science (68R05) Applications of graph theory to circuits and networks (94C15)

Related Items

Separating OR, SUM, and XOR circuits, Some combinatorial-algebraic problems from complexity theory, On complexity of linear operators on the class of circuits of depth 2, Circuit complexity of linear functions: gate elimination and feeble security, Min-rank conjecture for log-depth circuits, Gate Elimination for Linear Functions and New Feebly Secure Constructions, Entropy of operators or why matrix multiplication is hard for depth-two circuits, On set intersection representations of graphs, Representing \((0,1)\)-matrices by Boolean circuits, Efficient Construction of Rigid Matrices Using an NP Oracle, Cancellation-free circuits in unbounded and bounded depth, Arithmetic complexity of certain linear transformations, The arithmetic computational complexity of linear transforms