Speaker: Prof. Allan Borodin
Title: Conceptually simple algorithms: the what, the why, and the why not
In many applications, there are factors that go beyond computational efficiency. One such factor is the conceptual simplicity of the algorithm. For example, in auctions, buyers prefer easy to understand how mechanisms for allocating and pricing items.But what is a conceptually simple algorithm and at what cost (in performance, accuracy, efficiency) does it come? An ambitious research agenda would be to try define such a concept and study inherent tradeoffs. A more realistic agenda is to focus on the ``algorithmic paradigms'' that we study in courses such as CSC373. To that end, what is a greedy algorithm, local search, dynamic programming? When are such algorithms successful and when not? And does such introspection lead to new algorithms? We will present a brief introduction to this more modest research agenda.
Special reception to follow talk.
Undergraduate Theory Group