Representing (0, 1)-matrices by boolean circuits |
| |
Authors: | Stasys Jukna |
| |
Institution: | Institute of Mathematics and Computer Science, Vilnius, Lithuania |
| |
Abstract: | A boolean circuit represents an n by n(0,1)-matrix A if it correctly computes the linear transformation over GF(2) on all n unit vectors. If we only allow linear boolean functions as gates, then some matrices cannot be represented using fewer than Ω(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-2 circuit with O(nlnn) wires using multilinear polynomials over GF(2) of relatively small degree as gates. We then show that this cannot be substantially improved: If any two columns of an n by n(0,1)-matrix differ in at least d rows, then the matrix requires Ω(dlnn/lnlnn) wires in any depth-2 circuit, even if arbitrary boolean functions are allowed as gates. |
| |
Keywords: | Boolean circuits Linear circuits Hadamard matrices Lower bounds Sunflower lemma |
本文献已被 ScienceDirect 等数据库收录! |
|