|
University of Bonn -> Department of Computer Science -> Chair V | ||
CS-APX-Reports 1992 | Copyright 1992 University of Bonn, Department of Computer Science, Abt. V | |
8913
|
Simulating Threshold Circuits by Majority Circuits
Mikael Goldmann, Marek Karpinski [Download PostScript] [Download PDF] We prove that a single threshold gate can be simulated by an explicit polynomial size depth 2 majority circuit. In general we show that a depth $d$ threshold circuit can be simulated uniformly by a majority circuit of depth $d+1$. Goldmann, H{\aa}stad and Razborov showed in [9] that a non-uniform simulation exists. Our construction answers two open questions posed in [9]: we give an explicit construction whereas [9] uses a randomized existence argument, and we show that such a simulation is possible even if the depth $d$ grows with the number of variables $n$ (the simulation in [9] gives polynomial size circuits only when $d$ is constant). |
|
Last Change:
11/05/14 at 09:43:35
Deutsch |
University of Bonn -> Department of Computer Science -> Chair V |