@article{1412349,
      recid = {1412349},
      author = {Karchmer, Mauricio.},
      title = {Communication complexity : a new approach to circuit depth  /},
      publisher = {MIT Press,},
      address = {Cambridge, Mass. :},
      pages = {1 online resource (68 pages).},
      year = {1989},
      abstract = {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.Karchmer's approach looks at a computation device as  one that separates the words of a language from the  non-words. It views computation in a top down fashion,  making explicit the idea that flow of information is a  crucial term for understanding computation. Within this new  setting, Communication Complexity gives simpler proofs to  old results and demonstrates the usefulness of the approach  by presenting a depth lower bound for st-connectivity.  Karchmer concludes by proposing open problems which point  toward proving a general depth lower bound.Mauricio  Karchmer received his doctorate from Hebrew University and  is currently a Postdoctoral Fellow at the University of  Toronto. Communication Complexity received the 1988 ACM  Doctoral Dissertation Award.},
      url = {http://library.usi.edu/record/1412349},
}