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

Streubel, Jennifer jenn4 at bu.edu
Wed Nov 23 10:49:27 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, Peter Gacs, Lorenzo Orrechia, and Mark Crovella (chair)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/cs-talks/attachments/20161123/3cadff77/attachment.html>


More information about the cs-talks mailing list