Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
One of the major challenges of the research in circuit complexity is proving super-polynomial lower bounds for de Morgan formulas. Karchmer
et al
. (Comput Complex 5(3/4):191–204,
1995b
) suggested to approach this problem by proving that formula complexity behaves “as expected” with respect to the composition of functions
f
⋄
g
. They showed that this conjecture, if proved, would imply super-polynomial formula lower bounds.
The first step toward proving the KRW conjecture was made by Edmonds
et al
. (Comput Complex 10(3):210–246,
2001
), who proved an analogue of the conjecture for the composition of “universal relations.” In this work, we extend the argument of Edmonds
et al
. (
2001
) further to
f
⋄
g
where
f
is an arbitrary function and
g
is the parity function. While this special case of the KRW conjecture was already proved implicitly in Håstad’s work on random restrictions (Håstad in SIAM J Comput 27(1):48–64,
1998
), our proof seems more likely to be generalizable to other cases of the conjecture. In particular, our proof uses an entirely different approach, based on communication complexity technique of Karchmer & Wigderson in (SIAM J Discrete Math 3(2):255–265,
1990
). In addition, our proof gives a new structural result, which roughly says that the naive way for computing
f
⋄
g
is the
only
optimal way. Along the way, we obtain a new proof of the state-of-the-art formula lower bound of
n
3-
o
(1)
due to Håstad (
1998
).