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