Dinur, Irit ;
Meir, Or
Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity
Abstract
One of the major challenges of the research in circuit complexity is proving superpolynomial lower bounds for deMorgan 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 * g. They showed that this conjecture, if proved, would imply superpolynomial 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 * 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 * g is the only optimal way. Along the way, we obtain a new proof of the stateoftheart formula lower bound of n^{3o(1)} due to Hastad.
BibTeX  Entry
@InProceedings{dinur_et_al:LIPIcs:2016:5841,
author = {Irit Dinur and Or Meir},
title = {{Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity}},
booktitle = {31st Conference on Computational Complexity (CCC 2016)},
pages = {3:13:51},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770088},
ISSN = {18688969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5841},
URN = {urn:nbn:de:0030drops58412},
doi = {10.4230/LIPIcs.CCC.2016.3},
annote = {Keywords: Formula lower bounds, communication complexity, KarchmerWigderson games, KRW composition conjecture}
}
2016
Keywords: 

Formula lower bounds, communication complexity, KarchmerWigderson games, KRW composition conjecture 
Seminar: 

31st Conference on Computational Complexity (CCC 2016)

Issue date: 

2016 
Date of publication: 

2016 