TOWARD THE KRW COMPOSITION CONJECTURE: CUBIC FORMULA LOWER BOUNDS VIA COMMUNICATION COMPLEXITY

摘要

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 lozenge 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 lozenge 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 Hastad's work on random restrictions (Hastad 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): 255265, 1990). In addition, our proof gives a new structural result, which roughly says that the naive way for computing f lozenge 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 Hastad (1998).