Aarhus University Seal / Aarhus Universitets segl

Computing Symmetric Boolean Functions by Circuits with Few Exact Threshold Gates

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Department of Computer Science
We consider constant depth circuits augmented with few exact threshold gates with arbitrary weights. We prove strong (up to exponential) size lower bounds for such circuits computing symmetric Boolean functions. Our lower bound is expressed in terms of a natural parameter, the balance, of symmetric functions. Furthermore, in the quasi-polynomial size setting our results provides an exact characterization of the class of symmetric functions in terms of their balance.
Original languageEnglish
Title of host publicationComputing and Combinatorics : 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007. Proceedings
EditorsGuohui Lin
Number of pages11
PublisherSpringer
Publication year2007
Pages448-458
ISBN (print)978-3-540-73544-1
DOIs
Publication statusPublished - 2007
Event13th Annual International Computing and Combinatorics Conference, COCOON 2007 - Bannf, Canada
Duration: 16 Jul 200719 Jul 2007
Conference number: 13

Conference

Conference13th Annual International Computing and Combinatorics Conference, COCOON 2007
Nummer13
LandCanada
ByBannf
Periode16/07/200719/07/2007
SeriesLecture Notes in Computer Science
Volume4598

See relations at Aarhus University Citationformats

ID: 10561244