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的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。