Depth Two (n-2)-Majority Circuits for n-Majority

Kazuyuki AMANO  Masafumi YOSHIDA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E101-A   No.9   pp.1543-1545
Publication Date: 2018/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E101.A.1543
Type of Manuscript: Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
Boolean functions,  threshold circuits,  majority function,  

Full Text: PDF(242.8KB)
>>Buy this Article


Summary: 
We present an explicit construction of a MAJn-2 °MAJn-2 circuit computing MAJn for every odd n≥7. This gives a partial solution to an open problem by Kulikov and Podolskii (Proc. of STACS 2017, Article No.49).