Proof complexity as a computational lens lecture 6: Resolution and the clique problem [part 2]
Автор: MIAO Research
Загружено: 2025-11-17
Просмотров: 27
Monday Nov 17, 2025
Proof complexity as a computational lens
Lecture 6: Resolution and the clique problem [part 2]
(Jakob Nordström, University of Copenhagen and Lund University)
In this lecture, we continue our presentation of the n^Omega(k) length lower bound for regular resolution proofs of that Erdős–Rényi random graphs of the right density do not have k-cliques, a result that is due to Atserias, Bonacina, de Rezende, Lauria, Nordström, and Razborov. Since regular resolution is equivalent to read-once branching programs (ROBPs) for the falsified clause search problem, we phrase the lower bound in the language of ROBPs. We identify some key properties of random graphs, referred to as neighbour-denseness and clique-denseness, that allow us to prove a lower bound via a bottleneck counting argument over pairs of nodes in the branching program.
This is lecture 6 on the course "Proof complexity as a computational lens" (https://jakobnordstrom.se/teaching/pr...) given during the winter of 2025/26 at the University of Copenhagen and Lund University.
For more information about MIAO seminars and/or lectures, please visit https://jakobnordstrom.se/miao-seminars/ , or go to https://jakobnordstrom.se/miao-group/ to read more about the MIAO group.
#ProofComplexity
![Proof complexity as a computational lens lecture 6: Resolution and the clique problem [part 2]](https://ricktube.ru/thumbnail/Yvb88xvDQQM/hq720.jpg)
Доступные форматы для скачивания:
Скачать видео mp4
-
Информация по загрузке:
![Proof complexity as a computational lens lecture 5: Resolution and the clique problem [part 1]](https://ricktube.ru/thumbnail/7NmS1G9jjKg/mqdefault.jpg)