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

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

• 批准号: 2212136
• 负责人: Toniann Pitassi
• 金额: $ 60万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-06-15 至 2025-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2212136&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的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Lower Bounds for Polynomial Calculus with Extension Variables over FInite Fields

有限域上可拓变量多项式微积分的下界

• 发表时间: 2023
• 期刊: Proceedings IEEE Conference on Computational Complexity
• 作者: Impagliazzo, Russell;Mouli, Sasank;Pitassi, Toniann
• 通讯作者: Pitassi, Toniann

Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization

稳定就是稳定：可复制性、隐私性和自适应泛化之间的联系

• DOI: 10.1145/3564246.3585246
• 发表时间: 2023
• 期刊: STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing
• 作者: Bun, Mark;Gaboardi, Marco;Hopkins, Max;Impagliazzo, Russell;Lei, Rex;Pitassi, Toniann;Sivakumar, Satchit;Sorrell, Jessica
• 通讯作者: Sorrell, Jessica

Extremely Deep Proofs

极其深刻的证明

• DOI: 10.4230/lipics.itcs.2022.70
• 发表时间: 2022
• 期刊: Leibniz international proceedings in informatics
• 作者: Fleming, Noah and

The Strength of Equality Oracles in Communication

• DOI: 10.4230/lipics.itcs.2023.89
• 发表时间: 2022
• 作者: T. Pitassi;Morgan Shirley;A. Shraibman

On the algebraic proof complexity of Tensor Isomorphism

• DOI: 10.48550/arxiv.2305.19320
• 发表时间: 2023-05
• 期刊: Journal of Inorganic Materials
• 影响因子: 1.7
• 作者: Nicola Galesi;Joshua A. Grochow;T. Pitassi;Adrian She