Large Clique is Hard on Average for Resolution

Shuo Pang

doi:10.1007/978-3-030-79416-3_22

Large Clique is Hard on Average for Resolution

Shuo Pang^*

^*Corresponding author for this work

School of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

1 Citation (Scopus)

Abstract

We prove an exp(Ω(k^(1-ε))) resolution size lower bound for the k-Clique problem on random graphs, for (roughly speaking) k<n^1/3. Towards an optimal resolution lower bound of the problem (i.e. of type n^Ω(k)), we also extend the n^Ω(k)bound in [2] on regular resolution to a stronger model called a-irregular resolution, for k<n^1/3. This model is interesting in that all known CNF families separating regular resolution from general [1, 24] have short proofs in it.

Original language	English
Title of host publication	Computer Science – Theory and Applications
Subtitle of host publication	16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russia, June 28–July 2, 2021, Proceedings
Publisher	Springer, Cham
Pages	361-380
Number of pages	20
ISBN (Electronic)	9783030794163
ISBN (Print)	9783030794156
DOIs	https://doi.org/10.1007/978-3-030-79416-3_22
Publication status	Published - 17 Jun 2021
Event	16th International Computer Science Symposium in Russia, CSR 2021 - Sochi, Russian Federation Duration: 28 Jun 2021 → 2 Jul 2021 https://logic.pdmi.ras.ru/csr2021/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	12730
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th International Computer Science Symposium in Russia, CSR 2021
Country/Territory	Russian Federation
City	Sochi
Period	28/06/21 → 2/07/21
Internet address	https://logic.pdmi.ras.ru/csr2021/

Research Groups and Themes

Algorithms and Complexity
Resolution
k-Clique
Average-case Lower Bounds

Access to Document

10.1007/978-3-030-79416-3_22

Handle.net

Persistent link

Cite this

@inproceedings{1a19763140d8499fb2d4c37d9e1bb3b7,

title = "Large Clique is Hard on Average for Resolution",

abstract = "We prove an exp(Ω(k(1-ε))) resolution size lower bound for the k-Clique problem on random graphs, for (roughly speaking) k1/3. Towards an optimal resolution lower bound of the problem (i.e. of type nΩ(k)), we also extend the nΩ(k) bound in [2] on regular resolution to a stronger model called a-irregular resolution, for k1/3. This model is interesting in that all known CNF families separating regular resolution from general [1, 24] have short proofs in it.",

author = "Shuo Pang",

year = "2021",

month = jun,

day = "17",

doi = "10.1007/978-3-030-79416-3_22",

language = "English",

isbn = "9783030794156",

series = "Lecture Notes in Computer Science",

publisher = "Springer, Cham",

pages = "361--380",

booktitle = "Computer Science – Theory and Applications",

address = "Switzerland",

note = "16th International Computer Science Symposium in Russia, CSR 2021 ; Conference date: 28-06-2021 Through 02-07-2021",

url = "https://logic.pdmi.ras.ru/csr2021/",

}

Pang, S 2021, Large Clique is Hard on Average for Resolution. in Computer Science – Theory and Applications: 16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russia, June 28–July 2, 2021, Proceedings. Lecture Notes in Computer Science, vol. 12730, Springer, Cham, pp. 361-380, 16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russian Federation, 28/06/21. https://doi.org/10.1007/978-3-030-79416-3_22

Large Clique is Hard on Average for Resolution. / Pang, Shuo.
Computer Science – Theory and Applications: 16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russia, June 28–July 2, 2021, Proceedings. Springer, Cham, 2021. p. 361-380 (Lecture Notes in Computer Science; Vol. 12730).

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

TY - GEN

T1 - Large Clique is Hard on Average for Resolution

AU - Pang, Shuo

PY - 2021/6/17

Y1 - 2021/6/17

N2 - We prove an exp(Ω(k(1-ε))) resolution size lower bound for the k-Clique problem on random graphs, for (roughly speaking) k1/3. Towards an optimal resolution lower bound of the problem (i.e. of type nΩ(k)), we also extend the nΩ(k) bound in [2] on regular resolution to a stronger model called a-irregular resolution, for k1/3. This model is interesting in that all known CNF families separating regular resolution from general [1, 24] have short proofs in it.

AB - We prove an exp(Ω(k(1-ε))) resolution size lower bound for the k-Clique problem on random graphs, for (roughly speaking) k1/3. Towards an optimal resolution lower bound of the problem (i.e. of type nΩ(k)), we also extend the nΩ(k) bound in [2] on regular resolution to a stronger model called a-irregular resolution, for k1/3. This model is interesting in that all known CNF families separating regular resolution from general [1, 24] have short proofs in it.

UR - https://logic.pdmi.ras.ru/csr2021/

U2 - 10.1007/978-3-030-79416-3_22

DO - 10.1007/978-3-030-79416-3_22

M3 - Conference Contribution (Conference Proceeding)

SN - 9783030794156

T3 - Lecture Notes in Computer Science

SP - 361

EP - 380

BT - Computer Science – Theory and Applications

PB - Springer, Cham

T2 - 16th International Computer Science Symposium in Russia, CSR 2021

Y2 - 28 June 2021 through 2 July 2021

ER -