[cs-talks] PhD Thesis Defense, Jeffrey Finkelstein, Friday December 2nd, 2:00 Hariri Institute for Computing Seminar room MCS 180, 111 Cummington Mall

Steve Homer homer at cs.bu.edu
Wed Nov 30 08:43:48 EST 2016


                PhD Thesis Defense

      Parallelism With Limited Nondeterminism

                Jeffrey Finkelstein


Friday, December 2, 2016, 2:00 P.M.

Hariri Institute for Computing Seminar room MCS 180, 111 Cummington Mall
 
ABSTRACT

Computational complexity theory studies which computational problems can be solved with
limited access to resources. The past fifty years have seen a focus on the relationship
between intractable problems and efficient algorithms. However, the relationship between
inherently sequential problems and highly parallel algorithms has not been well studied. Are
there efficient but inherently sequential problems that admit some relaxed form of highly
parallel algorithm? In this dissertation, we develop the theory of structural complexity
around this relationship for three common types of computational problems.

Specifically, we show tradeoffs between time, nondeterminism, and parallelizability. By
clearly defining the notions and complexity classes that capture our intuition for
parallelizable and sequential problems, we create a comprehensive framework for rigorously
proving parallelizability and non-parallelizability of computational problems. The current
growth of multiprocessor systems highlights the need to consider whether otherwise tractable
problems can be effectively parallelized, and this framework provides the means to prove it.
The views adopted by this dissertation alternate approaches to solving sequential problems
using approximation, limited nondeterminism, and parameterization can be applied practically
throughout computer science.

Committee:

Steve Homer (major advisor), Ben Hescott (co-advisor), Peter Gacs, Lorenzo 
Orrechia, and Mark Crovella (chair)



More information about the cs-talks mailing list