Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 1992 Copyright 1992 Universität Bonn, Institut für Informatik, 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
 English
Universität Bonn -> Institut für Informatik -> Abteilung V