Some Meet-in-the-middle Circuit Lower Bounds

TY - GEN

T1 - Some Meet-in-the-middle Circuit Lower Bounds

AU - Hansen, K.A.

AU - Miltersen, P.B.

N1 - Conference code: 29

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-540-28629-5_24

DO - 10.1007/978-3-540-28629-5_24

M3 - Article in proceedings

T3 - Lecture Notes in Computer Science

SP - 334

EP - 345

BT - Mathematical Foundations of Computer Science 2004

A2 - Fiala, Jiri

A2 - Koubek, Vaclav

A2 - Kratochvil, Jan

PB - Springer

T2 - International Symposium on Mathematical Foundations of Computer Science. MFCS'04

Y2 - 22 August 2004 through 27 August 2004

ER -