Linear circuits over GF(2)

Noga Alon; Mauricio Karchmer; Avi Wigderson

doi:10.1137/0219074

Linear circuits over GF(2)

Noga Alon, Mauricio Karchmer, Avi Wigderson

Research output: Contribution to journal › Article › peer-review

20 Scopus citations

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	https://doi.org/10.1137/0219074
State	Published - 1990
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Computer Science
General Mathematics

Access to Document

10.1137/0219074

Cite this

@article{f07697a83f04473093910b9a3a736a15,

title = "Linear circuits over GF(2)",

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.",

author = "Noga Alon and Mauricio Karchmer and Avi Wigderson",

year = "1990",

doi = "10.1137/0219074",

language = "English (US)",

volume = "19",

pages = "1064--1067",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "6",

}

TY - JOUR

T1 - Linear circuits over GF(2)

AU - Alon, Noga

AU - Karchmer, Mauricio

AU - Wigderson, Avi

PY - 1990

Y1 - 1990

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0025640505&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025640505&partnerID=8YFLogxK

U2 - 10.1137/0219074

DO - 10.1137/0219074

M3 - Article

AN - SCOPUS:0025640505

SN - 0097-5397

VL - 19

SP - 1064

EP - 1067

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 6

ER -

Linear circuits over GF(2)

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this