Mathematical Sciences: Some Combinatorial Investigations Arising From Theoretical Computer Science

点击翻译按钮获取中文摘要

This award supports the research of Professor Michael Saks at Rutgers, the State University of New Jersey in New Brunswick. It is a twenty four month standard grant made by the Algebra and Number Theory Program in the Division of Mathematical Sciences and the Theoretical Computer Science Program in the Division of Computer Research. Professor Saks is a young mathematician who has burst onto the scene with his very important results which lie on the border between combinatorics and theoretical computer science. His work in the recent past dealt with existence theorems on partially ordered sets that were motivated by problems in the theory of searching and sorting algorithms. Some of his results were spectacular. In his current proposal he moves even more toward problems in combinatorics whose origin lies in computer science. He plans to analysize certain questions in distributed computing: the performance of tasks by a set of individual processors acting independently and communicating over some network. A critical issue for such distributed systems is reliabililty, that is, to design the system so that it still works even when some of the computers are faulty. This important research will undoubtably pay rich dividends.