We give new lower bounds for the fragments of the Ideal Proof System (IPS) introduced by Grochow and Pitassi (JACM 2018). The Ideal Proof System is a central topic in algebraic proof complexity developed in the context of Nullstellensatz refutation (Beame, Impagliazzo, Krajicek, Pitassi, Pudlak, FOCS 1994) and simulates Extended Frege efficiently. Our main results are as follows. 1. mult-IPS_{Lin'}: We prove nearly quadratic-size formula lower bound for multilinear refutation (over the Boolean hypercube) of a variant of the subset-sum axiom polynomial. Extending this, we obtain a nearly matching qualitative statement for a constant degree target polynomial. 2. IPS_{Lin'}: Over the fields of characteristic zero, we prove exponential-size sum-of-ROABPs lower bound for the refutation of a variant of the subset-sum axiom polynomial. The result also extends over the fields of positive characteristics when the target polynomial is suitably modified. The modification is inspired by the recent results (Hakoniemi, Limaye, Tzameret, STOC 2024 and Behera, Limaye, Ramanathan, Srinivasan, ICALP 2025). The mult-IPS_{Lin'} lower bound result is obtained by combining the quadratic-size formula lower bound technique of Kalorkoti (SICOMP 1985) with some additional ideas. The proof technique of IPS_{Lin'} lower bound result is inspired by the recent lower bound result of Chatterjee, Kush, Saraf and Shpilka (CCC 2024).


翻译:我们为Grochow和Pitassi(JACM 2018)提出的理想证明系统(IPS)片段给出了新的下界。理想证明系统是在零化子反驳(Beame, Impagliazzo, Krajicek, Pitassi, Pudlak, FOCS 1994)背景下发展起来的代数证明复杂性核心课题,并能高效模拟扩展弗雷格系统。我们的主要结果如下:1. mult-IPS_{Lin'}:针对子集和公理多项式的一个变体,我们证明了在布尔超立方上的多重线性反驳存在近二次规模的公式下界。通过扩展该结果,我们针对常数次目标多项式获得了近乎匹配的定性结论。2. IPS_{Lin'}:在特征为零的域上,我们证明了子集和公理多项式变体反驳的ROABP和存在指数规模下界。当目标多项式经过适当修改时,该结果也可推广至正特征域。此修改受到近期研究成果(Hakoniemi, Limaye, Tzameret, STOC 2024 以及 Behera, Limaye, Ramanathan, Srinivasan, ICALP 2025)的启发。mult-IPS_{Lin'}下界结果是通过将Kalorkoti(SICOMP 1985)的二次规模公式下界技术与若干新思路相结合而获得的。IPS_{Lin'}下界结果的证明技术则受到Chatterjee, Kush, Saraf和Shpilka(CCC 2024)近期下界成果的启发。

0
下载
关闭预览

相关内容

NeurIPS 是全球最受瞩目的AI、机器学习顶级学术会议之一,每年全球的人工智能爱好者和科学家都会在这里聚集,发布最新研究。NeurIPS 2019大会将在12月8日-14日在加拿大温哥华举行。据官方统计消息,NeurIPS今年共收到投稿6743篇,其中接收论文1428篇,接收率21.1%。官网地址:https://neurips.cc/

知识荟萃

精品入门和进阶教程、论文和代码整理等

更多

查看相关VIP内容、论文、资讯等
FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
34+阅读 · 2019年10月18日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
60+阅读 · 2019年10月17日
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
44+阅读 · 2019年1月3日
STRCF for Visual Object Tracking
统计学习与视觉计算组
15+阅读 · 2018年5月29日
Focal Loss for Dense Object Detection
统计学习与视觉计算组
12+阅读 · 2018年3月15日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
国家自然科学基金
13+阅读 · 2017年12月31日
国家自然科学基金
3+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
2+阅读 · 2014年12月31日
Arxiv
11+阅读 · 2019年6月19日
VIP会员
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
44+阅读 · 2019年1月3日
STRCF for Visual Object Tracking
统计学习与视觉计算组
15+阅读 · 2018年5月29日
Focal Loss for Dense Object Detection
统计学习与视觉计算组
12+阅读 · 2018年3月15日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
相关基金
国家自然科学基金
13+阅读 · 2017年12月31日
国家自然科学基金
3+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
2+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员