1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University2 Department of Computer Science, Science and Technology, Aarhus University3 Department of Computer Science, Science and Technology, Aarhus University
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.
Lecture Notes in Computer Science: 29th International Symposium, Mfcs 2004, Prague, Czech Republic, August 22-27, 2004. Proceedings, 2004, p. 334-345
Main Research Area:
Lecture Notes in Computer Science
International Symposium on Mathematical Foundations of Computer Science. MFCS'04, 2004