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.

私家侦探涉及一系列广泛的问题， 发展对计算本质的理解。 他在延长 代数方法的应用范围和随机化 他和他的合著者开发的程序， 算法 所寻求的算法的两个示例是：（1）a 最大匹配问题的确定性并行算法，以及 (2)一种近似矩阵积和式的随机算法。 他还在继续调查 这些问题已经引起了人们的注意。 两 这些问题的例子是：（1）确定是否有定向 图具有偶数长度的圈，并且 (2)最短向量问题 正在探索使用随机化可归约性作为一种工具， 处理第二个问题。 私家侦探被评为杰出的计算机科学家 总统青年调查员小组。