PYI: Algebraic Methods and Randomization for Obtaining Efficient Algorithms

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

The P.I. is involved with a wide range of problems fundamental to the developing understanding of the nature of computation. He is extending the range of application of the algebraic methods and the randomization procedures he and his coauthors have developed for obtaining efficient algorithms. Two examples of algorithms sought are: (1) a deterministic parallel algorithm for the maximum matching problem, and (2) a randomized algorithm for approximating the permanent of a matrix. He is also continuing his investigation of the complexity of computational problems that have received previous attention. Two examples of such problems are: (1) determining whether a directed graph has an even length cycle, and (2) the shortest vector problem. The use of randomized reducibilities is being explored as a tool for dealing with this second problem. The P.I. has been judged to be an outstanding computer scientist by the Presidential Young Investigator Panel.