Simulating Threshold Circuits by Majority Circuits (Extended Version)

TitleSimulating Threshold Circuits by Majority Circuits (Extended Version)
Publication TypeTechnical Report
Year of Publication1994
AuthorsGoldmann, M., & Karpinski M.
Other Numbers900

We prove that a single threshold gate with arbitrary weights 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, Hastad, and Razborov showed in [10] that a non-uniform simulation exists. Our construction answers two open questions posed in [10]: we give an explicit construction whereas [10] 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 [10] gives polynomial- size circuits only when d is constant).

Bibliographic Notes

ICSI Technical Report TR-94-030

Abbreviated Authors

M. Goldmann and M. Karpinski

ICSI Publication Type

Technical Report