Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Clique Is Hard on Average for Unary Sherali-Adams

De Rezende, Susanna F. LU orcid ; Potechin, Aaron and Risse, Kilian LU (2023) 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023 In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS p.12-25
Abstract

We prove that unary Sherali-Adams requires proofs of size nΩ(d) to rule out the existence of an nΘ(1)-clique in Erdős-Rényi random graphs whose maximum clique is of size d ≤ 2 log n. This lower bound is tight up to the multiplicative constant in the exponent. We obtain this result by introducing a technique inspired by pseudo-calibration which may be of independent interest. The technique involves defining a measure on monomials that precisely captures the contribution of a monomial to a refutation. This measure intuitively captures progress and should have further applications in proof complexity.

Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Clique, Proof Complexity, Unary Sherali Adams
host publication
Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023
series title
Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
pages
14 pages
publisher
IEEE - Institute of Electrical and Electronics Engineers Inc.
conference name
64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023
conference location
Santa Cruz, United States
conference dates
2023-11-06 - 2023-11-09
external identifiers
  • scopus:85182403637
ISSN
0272-5428
ISBN
9798350318944
DOI
10.1109/FOCS57990.2023.00008
language
English
LU publication?
yes
additional info
Publisher Copyright: © 2023 IEEE.
id
693be8c5-3a8f-4dec-9b36-8798a2fda2bc
date added to LUP
2024-01-28 15:06:58
date last changed
2025-10-14 11:10:13
@inproceedings{693be8c5-3a8f-4dec-9b36-8798a2fda2bc,
  abstract     = {{<p>We prove that unary Sherali-Adams requires proofs of size nΩ(d) to rule out the existence of an nΘ(1)-clique in Erdős-Rényi random graphs whose maximum clique is of size d ≤ 2 log n. This lower bound is tight up to the multiplicative constant in the exponent. We obtain this result by introducing a technique inspired by pseudo-calibration which may be of independent interest. The technique involves defining a measure on monomials that precisely captures the contribution of a monomial to a refutation. This measure intuitively captures progress and should have further applications in proof complexity.</p>}},
  author       = {{De Rezende, Susanna F. and Potechin, Aaron and Risse, Kilian}},
  booktitle    = {{Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023}},
  isbn         = {{9798350318944}},
  issn         = {{0272-5428}},
  keywords     = {{Clique; Proof Complexity; Unary Sherali Adams}},
  language     = {{eng}},
  pages        = {{12--25}},
  publisher    = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
  series       = {{Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS}},
  title        = {{Clique Is Hard on Average for Unary Sherali-Adams}},
  url          = {{http://dx.doi.org/10.1109/FOCS57990.2023.00008}},
  doi          = {{10.1109/FOCS57990.2023.00008}},
  year         = {{2023}},
}