Welcome to Jonas Conneryd's licentiate thesis seminar on Thursday May 8th at 10:30-13:00 in E:C

Thesis title: On the Average-Case Proof Complexity of Graph Coloring

Author: Jonas Conneryd, Department of Computer Science, Lund University

Faculty opponent: Prof. Nutan Limaye, IT University of Copenhagen

Examiner: Prof. Jacek Malec, LTH

Supervisor: Prof. Tatyana Turova, LU

Co-supervisor: Senior Lecturer Michael Doggett, LTH

Date and time: Thursday 8 May at 10:30

Location: E:C, E-huset, LTH, Klas Anshelms väg 10/Ole Römers väg 3, Lund

Link to download thesis: To be added

Abstract

For all k ≥ 3, we prove essentially optimal lower bounds for the size and degree required for the polynomial calculus proof system to refute the k-colorability of a sparse graph sampled either from the Erdős–Rényi distribution or the uniform distribution over regular graphs. Our results hold for both the Boolean encoding and the so-called roots-of-unity encoding of k-colorability.