### Abstract

For n = 2^{k}, 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}, S_{i,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.

Original language | English (US) |
---|---|

Pages (from-to) | 1064-1067 |

Number of pages | 4 |

Journal | SIAM Journal on Computing |

Volume | 19 |

Issue number | 6 |

DOIs | |

State | Published - Jan 1 1990 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Computer Science(all)
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Linear circuits over GF(2)'. Together they form a unique fingerprint.

## Cite this

Alon, N., Karchmer, M., & Wigderson, A. (1990). Linear circuits over GF(2).

*SIAM Journal on Computing*,*19*(6), 1064-1067. https://doi.org/10.1137/0219074