Collaborative Research: AF:Medium: Advancing the Lower Bound Frontier

合作研究：AF：中：推进下界前沿

• 批准号: 2212135
• 负责人: Russell Impagliazzo
• 金额: $ 60万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-06-15 至 2025-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2212135&HistoricalAwards=false
• 关键词: Collaborative; Research; AF; Medium; Advancing

The central problem in computational complexity theory is to develop the most efficient algorithms for important computational problems. To prove that an algorithm is the most efficient, the holy grail of complexity theory is to prove unconditional lower bounds, showing that any algorithm, however clever or sophisticated, will inherently require a certain amount of resources (hardware, or runtime) to solve. The goal of this research is to tackle the most basic challenge of proving circuit and runtime lower bounds for explicit problems, as well as similar challenges in proof and communication complexity lower bounds.In more detail, this project is focused on two approaches. The first approach involves exploiting the two-way connection between circuit lower bounds and meta-algorithms, algorithms whose inputs or outputs are circuits or other algorithm descriptions. Important examples of meta-algorithms are: circuit satisfiability, where the input is a circuit and the output is whether it is satisfiable; proof search, where the input is an unsatisfiable formula and the output is a small refutation of it in a proof system; and PAC learning, where the input consists of labelled examples of an unknown target function to be output. Often, paradoxically, efficient algorithms for meta-computational problems such as these lead to improved lower bounds and vice versa. The second approach is known as lifting, whereby lower bounds in a more complex model of computation are reduced to lower bounds in a simpler model. Through lifting and related ideas, circuit complexity has been related to proof complexity and communication complexity, and lower bounds have been improved for all three settings. The team of researchers will investigate a variety of ideas to extend and deepen these approaches to push past the current barriers in lower bounds. The research is also expected to develop improved algorithms for meta-algorithmic problems, which are of central importance for hardware and software verification, algorithmic learning, and a broad range of other applications.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

计算复杂性理论中的主要问题是为重要的计算问题开发最有效的算法。为了证明算法是最有效的，复杂性理论的圣杯是证明无条件的下限，表明任何算法，无论多么聪明或精致，都会固有地需要一定数量的资源（硬件或运行时）才能解决。这项研究的目的是应对明确问题的证明电路和运行时下限的最基本挑战，以及在证明和沟通复杂性下的类似挑战下降。在更详细的情况下，该项目集中在两种方法上。第一种方法涉及利用电路下限和元偏之间的双向连接，输入或输出的算法是电路或其他算法描述。 元算法的重要示例是：电路满足性，输入是电路，输出是令人满意的；证明搜索，其中输入是一个不满意的公式，而输出是在证明系统中的一小部分反驳；和PAC学习，其中输入由要输出的未知目标函数的标记示例组成。通常，诸如元计算问题的矛盾，有效的算法会导致下限改善，反之亦然。第二种方法称为举重，在更复杂的计算模型中，在更简单的模型中将下限降低为下限。 通过提升和相关的想法，电路复杂性与证明复杂性和沟通复杂性有关，并且在所有三种设置中都改善了下限。研究人员团队将调查各种思想，以扩展和加深这些方法，以将当前的障碍推向下限。 预计这项研究还将开发用于元算象问题的改进算法，这对于硬件和软件验证，算法学习和其他广泛的其他应用程序至关重要。该奖项反映了NSF的法定任务，并通过使用该基金会的知识优点和广泛的影响来评估NSF的法定任务，并被认为是值得的。