Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR16-035 | 26th January 2017 16:09

Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity

RSS-Feed




Revision #2
Authors: Irit Dinur, Or Meir
Accepted on: 26th January 2017 16:09
Downloads: 103
Keywords: 


Abstract:

One of the major challenges of the research in circuit complexity is proving super-polynomial lower bounds for de-Morgan formulas. Karchmer, Raz, and Wigderson (Computational Complexity 5(3/4)) suggested to approach this problem by proving that formula complexity behaves "as expected" with respect to the composition of functions $f \diamond 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. (Computational Complexity 10(3)), who proved an analogue of the conjecture for the composition of "universal relations". In this work, we extend the argument of Edmonds et. al. further to $f \diamond g$ where $f$ is an arbitrary function and $g$ is the parity function.

Abstract While this special case of the KRW conjecture was already proved implicitly in H{\aa}stad's work on random restrictions (SICOMP 28(1)), 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 and Wigderson (SIAM J. Discrete Math. 3(2)). In addition, our proof gives a new structural result, which roughly says that the naive way for computing $f \diamond 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{\aa}stad.



Changes to previous version:

Simplified and improved the $f$-stage lemma, using an idea of Osamu Watanabe and Masaki Yamamoto.


Revision #1 to TR16-035 | 12th March 2016 06:56

Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity





Revision #1
Authors: Irit Dinur, Or Meir
Accepted on: 12th March 2016 06:56
Downloads: 558
Keywords: 


Abstract:

One of the major challenges of the research in circuit complexity is proving super-polynomial lower bounds for de-Morgan formulas. Karchmer, Raz, and Wigderson suggested to approach this problem by proving that formula complexity behaves "as expected'' with respect to the composition of functions $f\circ 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., who proved an analogue of the conjecture for the composition of "universal relations''. In this work, we extend the argument of Edmonds et. al. further to $f \circ 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, 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 and Wigderson. In addition, our proof gives a new structural result, which roughly says that the naive way for computing $f \circ 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.



Changes to previous version:

minor corrections


Paper:

TR16-035 | 11th March 2016 21:57

Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity





TR16-035
Authors: Irit Dinur, Or Meir
Publication: 11th March 2016 21:58
Downloads: 395
Keywords: 


Abstract:

One of the major challenges of the research in circuit complexity is proving super-polynomial lower bounds for de-Morgan formulas. Karchmer, Raz, and Wigderson suggested to approach this problem by proving that formula complexity behaves "as expected'' with respect to the composition of functions $f\circ 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., who proved an analogue of the conjecture for the composition of "universal relations''. In this work, we extend the argument of Edmonds et. al. further to $f \circ 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, 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 and Wigderson. In addition, our proof gives a new structural result, which roughly says that the naive way for computing $f \circ 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.



ISSN 1433-8092 | Imprint