Publication Details
Title: Simulating Threshold Circuits by Majority Circuits
Author: M. Goldmann and M. Karpinski
Group: ICSI Technical Reports
Date: December 1992
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-080.pdf
Overview:
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, Hastad and Razborov demonstrated that a non-uniform simulation exists. Our construction answers two open questions posed in their work: We give an explicit construction whereas Goldmann, Hastad and Razborov use 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 their work gives polynomial size circuits only when d is constant).
Bibliographic Information:
ICSI Technical Report TR-92-080
Bibliographic Reference:
M. Goldmann and M. Karpinski. Simulating Threshold Circuits by Majority Circuits. ICSI Technical Report TR-92-080, December 1992
Author: M. Goldmann and M. Karpinski
Group: ICSI Technical Reports
Date: December 1992
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-080.pdf
Overview:
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, Hastad and Razborov demonstrated that a non-uniform simulation exists. Our construction answers two open questions posed in their work: We give an explicit construction whereas Goldmann, Hastad and Razborov use 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 their work gives polynomial size circuits only when d is constant).
Bibliographic Information:
ICSI Technical Report TR-92-080
Bibliographic Reference:
M. Goldmann and M. Karpinski. Simulating Threshold Circuits by Majority Circuits. ICSI Technical Report TR-92-080, December 1992