Computing symmetrie functions with AND/OR circuits and a single MAJORITY gate

Zhi Li Zhang, David A.Mix Barrington, Jun Tarui

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

Fagin et al. characterized those symmetric Boolean functions which can be computed by small AND/OR circuits of constant depth and unbounded fan-in. Here we provide a similar characterization for d-perceptrons-AND/OR circuits of constant depth and unbounded fan-in with a single MAJORITY gate at the output. We show that a symmetric function has small (quasipolynomial, or 2log O(1) n size) d-perceptrons iff it has only poly-log many sign changes (i.e., it changes value logO(1) n times as the number of positive inputs varies from zero to n). A consequence of the lower bound is that a recent construction of Beigel is optimal. He showed how to convert a constant-depth unbounded fan-in AND/OR circuit with poly-log many MAJORITY gates into an equivalent d-perceptron-we show that more than poly-log MAJORITY gates cannot in general be converted to one.

Original languageEnglish (US)
Title of host publicationSTACS 1993 - 10th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
EditorsPatrice Enjalbert, Alain Finkel, Klaus W. Wagner
PublisherSpringer Verlag
Pages535-544
Number of pages10
ISBN (Print)9783540565031
DOIs
StatePublished - 1993
Event10th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1993 - Wurzburg, Germany
Duration: Feb 25 1993Feb 27 1993

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume665 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other10th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1993
Country/TerritoryGermany
CityWurzburg
Period2/25/932/27/93

Bibliographical note

Funding Information:
The first author was supported by grants CCR-8812567 and CCR-9008416. The second author was supported by NSF Computer and Computation Theory grants CCR-8922098 and CCR-9207829. The third author was supported in part by the ESPRIT IIBRA Programme of the EC under contract 7141 (ALCOM II).

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1993.

Fingerprint

Dive into the research topics of 'Computing symmetrie functions with AND/OR circuits and a single MAJORITY gate'. Together they form a unique fingerprint.

Cite this