Monotone Circuit Lower Bounds from Resolution

被引：6

作者：

Garg, Ankit ^{[1
]}

Goos, Mika ^{[2
]}

Kamath, Pritish ^{[3
]}

Sokolov, Dmitry ^{[4
]}

机构：

[1] Microsoft Res India, Bengaluru, Karnataka, India

[2] Ecole Polytech Fed Lausanne, Theory Grp, Lausanne, Switzerland

[3] Toyota Technol Inst Chicago, Chicago, IL USA

[4] KTH Royal Inst Technol, Stockholm, Sweden

来源：

THEORY OF COMPUTING | 2020年 / 16卷 / 16期

基金：

瑞典研究理事会;

关键词：

circuit complexity; communication complexity; proof complexity; COMMUNICATION; COMPLEXITY; PROOFS; SIZE; HARD;

D O I：

10.4086/toc.2020.v016a013

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

For any unsatisfiable CNF formula F that is hard to refute in the Resolution proof system, we show that a gadget-composed version of F is hard to refute in any proof system whose lines are computed by efficient communication protocols-or, equivalently, that a monotone function associated with F has large monotone circuit complexity. Our result extends to monotone real circuits, which yields new lower bounds for the Cutting Planes proof system.

引用

页数：30

共 50 条

[1] Monotone Circuit Lower Bounds from Resolution
Garg, Ankit
Goos, Mika
Kamath, Pritish
Sokolov, Dmitry
STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2018, : 902 - 911
[2] Monotone Circuit Lower Bounds from Robust Sunflowers
Cavalar, Bruno Pasqualotto
Kumar, Mrinal
Rossman, Benjamin
ALGORITHMICA, 2022, 84 (12) : 3655 - 3685
[3] Monotone Circuit Lower Bounds from Robust Sunflowers
Bruno Pasqualotto Cavalar
Mrinal Kumar
Benjamin Rossman
Algorithmica, 2022, 84 : 3655 - 3685
[4] Strongly Exponential Lower Bounds for Monotone Computation
Pitassi, Toniann
Robere, Robert
STOC'17: PROCEEDINGS OF THE 49TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2017, : 1246 - 1255
[5] Monotone Projection Lower Bounds from Extended Formulation Lower Bounds
Grochow, Joshua A.
THEORY OF COMPUTING, 2017, 13 : 1 - 15
[6] Circuit lower bounds from learning-theoretic approaches
Kawachi, Akinori
THEORETICAL COMPUTER SCIENCE, 2018, 733 : 83 - 98
[7] LOCALITY FROM CIRCUIT LOWER BOUNDS
Anderson, Matthew
van Melkebeek, Dieter
Schweikardt, Nicole
Segoufin, Luc
SIAM JOURNAL ON COMPUTING, 2012, 41 (06) : 1481 - 1523
[8] On Uniformity and Circuit Lower Bounds
Santhanam, Rahul
Williams, Ryan
COMPUTATIONAL COMPLEXITY, 2014, 23 (02) : 177 - 205
[9] STRONG AVERAGE-CASE CIRCUIT LOWER BOUNDS FROM NONTRIVIAL DERANDOMIZATION
Chen, Lijie
Ren, Hanlin
SIAM JOURNAL ON COMPUTING, 2022, 51 (03) : 115 - 173
[10] Lower bounds for monotone counting circuits
Jukna, Stasys
DISCRETE APPLIED MATHEMATICS, 2016, 213 : 139 - 152

← 1 2 3 4 5 →