Skip to main content
Upcoming Events:

Dept. Seminar: Avery Miller, University of Manitoba

Date & Time:
   Add All to Calendar
Location:

ITB-201

Event Contact:

Fei Chiang, Peter Robinson

Overview

Algorithms with Advice: How Information Can('t) Help

Solving a problem efficiently (if at all) depends on several factors, such as which operations an algorithm can perform, and various aspects of the environment such as faults. In some cases, the information that an algorithm has access to can play a central role. As an example, routing packets in large networks could be improved if every router always had a complete and up-to-date map of the entire network. Helpful information can be expensive to acquire and store, but perhaps even a small amount of additional information could help algorithms significantly. "Algorithms with advice" is a formal framework that attempts to reveal the relationship between quantities of information and algorithmic performance for a given problem. Some results demonstrate that certain kinds of information can be helpful, but, more interestingly, other results prove that even large amounts of ANY information cannot significantly help! This talk will provide an introductory overview of how and why people study algorithms with advice, with some examples from recent results.

BIO: Avery Miller is currently an Assistant Professor at the University of Manitoba. His academic journey started at the University of Waterloo, where he received a Bachelor of Mathematics degree, and went on to complete his Ph.D. in Computer Science at the University of Toronto in 2014. He held postdoctoral fellowships at Tel Aviv University and L'Université du Québec en Outaouais before joining the Department of Computer Science at U of M. His main research interests involve algorithms for distributed systems, with an emphasis on proving upper and lower bounds on the complexity of tasks in communication networks and other graph-based models.