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.

理论计算机科学的一个主要焦点是确定解决特定计算问题所需的“工作”，效率是通常的目标。解决一个问题所需的工作，或“运行时间”，通常用与问题大小相关的数字n来表示。 一个问题是“容易”的，如果它可以用“快速”算法解决（即其运行时间是n中的多项式）。快速算法是许多日常计算的核心，例如Web搜索引擎。 相反，对于某些问题，运行时间是n的指数函数;因此即使是中等大小的实例在实践中也是不可解的。对于其他问题，包括那些在类称为“NP”，运行时间和大小之间的确切关系仍然未知。 理解和映射可行问题和不可行问题之间的边界是计算复杂性的领域。P类问题可以在多项式时间内解决; NP类问题，可以在多项式时间内检查候选解，今天不能在多项式时间内解决，因此是不可行的。减轻这种不可行性的一种方法是获得一个好的但近似的解决方案。 由于近似的质量可能会有很大的不同，一个明显的问题是如何计算可行的算法可以近似精确的解决方案。一个重要的问题是知道算法是否达到了最佳性能;如果不是，应该寻找更好的算法。PI提出的研究涉及确定计算上可行的最佳近似比（这相当于证明任何更好的比都不可行）。事实证明，这些比率可以精确地分类，这项研究与数学，特别是傅立叶分析和几何学有几个联系。过去二十年来，在这些问题上取得了巨大进展，目前的建议旨在确定和应对仍然存在的若干挑战。该提案的研究目标将与教学、辅导和传播活动相结合。研究将涉及研究生和博士后研究员的参与。PI计划在研究生水平开发研究课程，介绍萌芽研究人员到该地区。传播活动将包括撰写简要文章和一本介绍性书籍以及组织讲习班。PI将欢迎任何机会来指导可能有兴趣接触研究的本科生（和高中）学生。