Linear Circuits over \operatorname{GF}(2)
From MaRDI portal
DOI10.1137/0219074zbMATH Open0712.05015OpenAlexW1514412042MaRDI QIDQ3496345FDOQ3496345
Authors: Noga Alon, A. 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
Recommendations
- On complexity of linear operators on the class of circuits of depth 2
- On the Complexity of Matrix Product
- Lower bounds for matrix product, in bounded depth circuits with arbitrary gates
- Representing \((0,1)\)-matrices by Boolean circuits
- A \(5n - o(n)\) lower bound on the circuit size over \(U _{2}\) of a linear Boolean function
Combinatorics in computer science (68R05) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Applications of graph theory to circuits and networks (94C15)
Cited In (19)
- On set intersection representations of graphs
- The arithmetic computational complexity of linear transforms
- On the Complexity of Matrix Product
- Separating OR, SUM, and XOR circuits
- Title not available (Why is that?)
- On complexity of linear operators on the class of circuits of depth 2
- Arithmetic complexity of certain linear transformations
- A note on the use of determinant for proving lower bounds on the size of linear circuits
- Efficient Construction of Rigid Matrices Using an NP Oracle
- A \(5n - o(n)\) lower bound on the circuit size over \(U _{2}\) of a linear Boolean function
- Some combinatorial-algebraic problems from complexity theory
- Cancellation-free circuits in unbounded and bounded depth
- Cancellation-free circuits in unbounded and bounded depth
- Gate elimination for linear functions and new feebly secure constructions
- Representing \((0,1)\)-matrices by Boolean circuits
- Circuit complexity of linear functions: gate elimination and feeble security
- Title not available (Why is that?)
- Min-rank conjecture for log-depth circuits
- Entropy of operators or why matrix multiplication is hard for depth-two circuits
This page was built for publication: Linear Circuits over $\operatorname{GF}(2)$
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3496345)
