Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

- Anna Gál, United States
- Kristoffer Arnsfelt Hansen
- Michal Koucký, Czech Republic
- Pavel Pudlák, Czech Republic
- Emanuele Viola, United States

We bound the minimum number w of wires needed to compute any (asymptotically good) error-correcting code

C:01(n)01n with minimum distance (n),

using unbounded fan-in circuits of depth d with arbitrary gates. Our main results are:

(1) If d=2 then w=(n(lognloglogn)2) .

(2) If d=3 then w=(nlglgn).

(3) If d=2k or d=2k+1 for some integer k2 then w=(nk(n)), where 1(n)=logn , i+1(n)=i(n), and the operation gives how many times one has to iterate the function i to reach a value at most 1 from the argument n.

(4) If d=logn then w=O(n).

Each bound is obtained for the first time in this paper.

For depth d=2,

our (n(lognloglogn)2) lower bound gives the

largest known lower bound for computing any linear map,

improving on the (nlg32n) bound of Pudlak and Rodl (Discrete Mathematics '94).

We find the upper bounds surprising.

They imply that a (necessarily dense) generator matrix

for the code can be written as the product of two sparse matrices.

The upper bounds are non-explicit: we show the existence of

circuits (consisting of only XOR gates) computing good codes

within the stated bounds.

Using a result by Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC '08),

we also obtain similar bounds for computing pairwise-independent hash

functions.

Furthermore, we identify a new class of superconcentrator-like graphs with connectivity properties distinct from previously-studied ones.

C:01(n)01n with minimum distance (n),

using unbounded fan-in circuits of depth d with arbitrary gates. Our main results are:

(1) If d=2 then w=(n(lognloglogn)2) .

(2) If d=3 then w=(nlglgn).

(3) If d=2k or d=2k+1 for some integer k2 then w=(nk(n)), where 1(n)=logn , i+1(n)=i(n), and the operation gives how many times one has to iterate the function i to reach a value at most 1 from the argument n.

(4) If d=logn then w=O(n).

Each bound is obtained for the first time in this paper.

For depth d=2,

our (n(lognloglogn)2) lower bound gives the

largest known lower bound for computing any linear map,

improving on the (nlg32n) bound of Pudlak and Rodl (Discrete Mathematics '94).

We find the upper bounds surprising.

They imply that a (necessarily dense) generator matrix

for the code can be written as the product of two sparse matrices.

The upper bounds are non-explicit: we show the existence of

circuits (consisting of only XOR gates) computing good codes

within the stated bounds.

Using a result by Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC '08),

we also obtain similar bounds for computing pairwise-independent hash

functions.

Furthermore, we identify a new class of superconcentrator-like graphs with connectivity properties distinct from previously-studied ones.

Original language | English |
---|---|

Journal | Electronic Colloquium on Computational Complexity |

Volume | 18 |

Issue | 150 |

Number of pages | 33 |

ISSN | 1433-8092 |

Publication status | Published - 2011 |

See relations at Aarhus University Citationformats

ID: 41569512