Complexity of Boolean Functions on PRAMs 
                        -- Lower Bound Techniques

                              Miroslaw Kutylowski

Determining time necessary for computing important functions on parallel
machines  is one of the most important problems in complexity theory for
parallel algorithms. Recently, a substantial progress has been  made  in
this  area.  In this survey paper, we discuss the results that have been
obtained for three types of parallel  random  access  machines  (PRAMs):
CREW, ROBUST and EREW.