For n = 2k, let S be an n × n matrix whose rows and columns are indexed by GF(2)k and, for i, j member of GF(2)k, Si,j = 〈i,j〉, the standard inner product. Size-depth trade-offs are investigated for computing Sx with circuits using only linear operations. In particular, linear size circuits with depth bounded by the inverse of an Ackerman function are constructed, and it is shown that depth two circuits require Ω(n log n) size. The lower bound applies to any Hadamard matrix.
All Science Journal Classification (ASJC) codes
- Computer Science(all)