Skip navigation

Mauricio Karchmer

Titles by This Author

A New Approach to Circuit Depth

Communication Complexity describes a new intuitive model for studying circuit networks that captures the essence of circuit depth. Although the complexity of boolean functions has been studied for almost 4 decades, the main problems the inability to show a separation of any two classes, or to obtain nontrivial lower bounds remain unsolved. The communication complexity approach provides clues as to where to took for the heart of complexity and also sheds light on how to get around the difficulty of proving lower bounds.