PYI: Algebraic Methods and Randomization for Obtaining Efficient Algorithms

pi涉及的问题范围广泛，对发展对计算本质的理解至关重要。他正在扩展代数方法和随机化程序的应用范围，他和他的合作者已经开发了有效的算法。所寻求的算法的两个例子是：(1)最大匹配问题的确定性并行算法，以及(2)近似矩阵永久值的随机算法。他还在继续研究先前受到关注的计算问题的复杂性。这类问题的两个例子是：(1)确定有向图是否具有偶数长度的循环，以及(2)最短向量问题。人们正在探索使用随机化约性作为处理第二个问题的工具。他被总统青年调查委员会评为杰出的计算机科学家。

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.