Some Meet-in-the-middle Circuit Lower Bounds

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

  • Department of Computer Science

We observe that a combination of known top-down and bottom-up lower bound techniques of circuit complexity may yield new circuit lower bounds.
An important example is this: Razborov and Wigderson showed that a certain function f in ACC 0 cannot be computed by polynomial size circuits consisting of two layers of MAJORITY gates at the top and a layer of AND gates at the bottom. We observe that a simple combination of their result with the Håstad switching lemma yields the following seemingly much stronger result: The same function f cannot be computed by polynomial size circuits consisting of two layers of MAJORITY gates at the top and an arbitrary AC 0 circuit feeding the MAJORITY gates.

Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2004 : 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004. Proceedings
EditorsJiri Fiala, Vaclav Koubek, Jan Kratochvil
Number of pages12
PublisherSpringer
Publication year2004
Pages334-345
DOIs
Publication statusPublished - 2004
EventInternational Symposium on Mathematical Foundations of Computer Science. MFCS'04 - Prag, Czech Republic
Duration: 22 Aug 200427 Aug 2004
Conference number: 29

Conference

ConferenceInternational Symposium on Mathematical Foundations of Computer Science. MFCS'04
Nummer29
LandCzech Republic
ByPrag
Periode22/08/200427/08/2004
SeriesLecture Notes in Computer Science
Volume3153
ISSN0302-9743

See relations at Aarhus University Citationformats

ID: 281986