Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648866 | Discrete Mathematics | 2010 | 4 Pages |
A boolean circuit represents an nn by nn(0,1)(0,1)-matrix AA if it correctly computes the linear transformation y→=Ax→ over GF(2)GF(2) on all nn unit vectors. If we only allow linear boolean functions as gates, then some matrices cannot be represented using fewer than Ω(n2/lnn)Ω(n2/lnn) wires. We first show that using non-linear gates one can save a lot of wires: any matrix can be represented by a depth-22 circuit with O(nlnn)O(nlnn) wires using multilinear polynomials over GF(2)GF(2) of relatively small degree as gates. We then show that this cannot be substantially improved: If any two columns of an nn by nn(0,1)(0,1)-matrix differ in at least dd rows, then the matrix requires Ω(dlnn/lnlnn)Ω(dlnn/lnlnn) wires in any depth-22 circuit, even if arbitrary boolean functions are allowed as gates.