Thesis Defense: The Complexity of Joint Computation
Speaker: Andrew Drucker , CSAIL, MIT
Date: April 30 2012
Time: 11:00AM to 12:00PM
Location: 32-D463 (Star seminar room)
Contact: Andrew Drucker, adrucker@mit.edu
Joint computation is the common scenario in which we have multiple computational tasks to perform in tandem. A fundamental question arises: when can we cleverly combine computations, to perform them with greater efficiency or reliability than by tackling them separately?
The question has two basic variants (each long-studied). In the first case, the inputs to the multiple computations are independent of each other. Intuitively we feel that joint computation cannot help us too much here, but things are deceptively subtle. In the second, “dependent” case, the computations depend on a shared input; the challenge is to understand the kinds of computational synergies that can arise.
I will describe my work studying the power and, especially, the limits of efficient joint computation, within several machine models--query algorithms, circuits, and Turing machines.
See other events that are part of
See other events happening in April 2012
