AF: Small: Challenges in Hardness of Approximation

AF：小：近似难度的挑战

• 批准号: 1422159
• 负责人: Subhash Khot
• 金额: $ 49.59万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1422159&HistoricalAwards=false
• 关键词: AF; Small; Challenges; Hardness; Approximation

A major focus in theoretical computer science is to determine the ``work" required to solve specific computational problems, efficiency being the usual goal. The work needed to solve a problem, or ``running time'', is often expressed in terms of a number n related to the problem size. A problem is ``easy'' if it is solvable by a ``fast'' algorithm (i.e. whose running time is a polynomial in n). Fast algorithms lie at the heart of much everyday computation, such as Web search engines. In contrast, for certain problems the running time is, unavoidably, an exponential function of n; hence even medium-size instances are unsolvable in practice. For other problems, including those in the class called ``NP", the exact relationship between running time and size remains unknown. Understanding and mapping the boundary between feasible and infeasible problems is the domain of computational complexity.Problems in the class ``P'' can be solved in polynomial time; problems in ``NP'', for which a candidate solution can be checked in polynomial time, cannot be solved in polynomial time today and are therefore infeasible. One way to mitigate this infeasibility is to obtain a good but approximate solution. Since the quality of an approximation may vary widely, an obvious question is how well a computationally feasible algorithm can approximate the exact solution. A significant issue is knowing whether the algorithm achieves the best possible performance; if not, a better algorithm should be sought.PI's proposed research involves determining the best approximation ratio that is computationally feasible (which amounts to proving that any better ratio is not feasible). It turns out that these ratios can be classified precisely and this research has several connections to mathematics, especially Fourier analysis and geometry. The last two decades have seen a huge progress on these questions and the current proposal is aimed at identifying and working on several challenges that are still wide open. The research goals of the proposal will be integrated with teaching, mentoring and dissemination activities. The research will involve participation of graduate students and post-doctoral fellows. The PI plans to develop research courses at graduate level to introduce budding researchers to the area. The dissemination activities will involve writing expository articles and an introductory book and organizing workshops. The PI will welcome any opportunities to guide under-graduate (and high-school) students who might be interested in having research exposure.

A major focus in theoretical computer science is to determine the ``work" required to solve specific computational problems, efficiency being the usual goal. The work needed to solve a problem, or ``running time'', is often expressed in terms of a number n related to the problem size. A problem is ``easy'' if it is solvable by a ``fast'' algorithm (i.e. whose running time is a polynomial in n).快速的算法是许多日常计算的核心，例如，对于某些问题而言，不可避免地，n的指数功能是中等大小的实例； 理解和映射可行和不可行的问题之间的边界是计算复杂性的领域。类``p''中的问题可以在多项式时间内解决。 ``np''中的问题，可以在多项式时间内检查候选解决方案，因此在今天的多项式时间内无法解决，因此是不可行的。减轻这种不可行性的一种方法是获得良好但近似的解决方案。 由于近似值的质量可能会差异很大，因此一个明显的问题是计算可行算法如何近似精确解决方案。一个重要的问题是知道该算法是否实现了最佳性能。如果不是，则应寻求更好的算法。PI的研究涉及确定计算上可行的最佳近似比（这相当于证明任何更好的比率是不可行的）。事实证明，这些比率可以精确地分类，这项研究与数学有多种联系，尤其是傅立叶分析和几何形状。在过去的二十年中，在这些问题上取得了巨大进展，目前的提案旨在识别和努力处理一些仍在敞开的挑战。该提案的研究目标将与教学，指导和传播活动相结合。这项研究将涉及研究生和博士后研究员的参与。 PI计划在研究生一级开发研究课程，以向该地区介绍萌芽的研究人员。传播活动将涉及撰写说明文章和介绍性书和组织研讨会。 PI将欢迎任何机会指导可能有兴趣进行研究曝光的学生（和高中生）学生。