Linear circuits over GF(2)

Noga Alon, Mauricio Karchmer, Avi Wigderson

Research output: Contribution to journalArticle

19 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1064-1067
Number of pages4
JournalSIAM Journal on Computing
Volume19
Issue number6
DOIs
StatePublished - Jan 1 1990
Externally publishedYes

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