Linear circuits over GF(2)

Noga Alon, Mauricio Karchmer, Avi Wigderson

Research output: Contribution to journalArticlepeer-review

20 Scopus citations


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
Issue number6
StatePublished - 1990
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics


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

Cite this