
University of Bonn > Department of Computer Science > Chair V  
CSReports 1992  Copyright 1992 University of Bonn, Department of Computer Science, Abt. V  
8583

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 nonuniform 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 