PYI: Algebraic Methods and Randomization for Obtaining Efficient Algorithms

PYI：获得高效算法的代数方法和随机化

• 批准号: 8552938
• 负责人: Vijay Vazirani
• 金额: $ 21.2万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1987
• 资助国家: 美国
• 起止时间: 1987-08-15 至 1993-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8552938&HistoricalAwards=false
• 关键词: PYI; Algebraic; Methods; Randomization; Obtaining

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.

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