This research focuses on algorithms that work limited information. Three topics are addressed, and each is motivated by an application in online or distributed computation. These topics include: (1) Distributed computation where a group of agents must collectively solve a problem. Each agent receives part of the input, and a graph is used to represent knowledge that is shared between the agents. The goal is to determine how to use shared information between the agents as well as to determine the value of sharing information. (2) These issues will be addressed with respect to problems in distributed job scheduling and network routing. Metrical Task Systems where the set of tasks (inputs to the system) are restricted. The restriction on the input is part of the description of the system. A unified approach will be developed to a variety of online problems by developing a general, simple algorithm which uses the system specification to approximate the best online algorithm for each particular system. (3) The use of a statistical adversary, which provides a way of bringing theoretical results in online algorithms closer to practical concerns by considering only those inputs which exhibit typical statistical features. It is a middle ground between probabilistic analysis and competitive analysis where the input is generated by an unlimited adversary. The use of a statistical adversary for problems in finance and computer systems will be considered. Interactive activities include: teaching a research seminar in online algorithms; leading weekly meetings with computer theory students to discuss research problems; involvement into the Columbia Chapter of the Society of Women Engineers; & women in the Computer Science Department.
