Joint Computer Science Speaking Skills Talk / Theory Lunch Seminar
— 1:00pm
Location:
In Person
-
Gates Hillman 8102
Speaker:
BERNARDO SUBERCASEAUX
,
Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://bsubercaseaux.github.io/
SAT-Solving for the Packing Chromatic Number of the Infinite Grid
This talk aims to illustrate the effectiveness of automated reasoning techniques in solving hard combinatorial problems arising from discrete mathematics. In particular, we will go through different aspects of modern SAT-solving such as encodings, symmetry breaking, and parallelism, which turn out to be key for solving very large instances related to coloring problems.
Our tour through such automated reasoning techniques will be guided by the problem of determining the packing chromatic number of the infinite grid, which we settled in 2023 to be 15, thus finally closing a sequence of work that started in 2002 by the seminal work of Goddard et al.
Joint with the Theory Lunch Seminar
Presented in Partial Fulfillment of the CSD Speaking Skills Requirement
Event Website:
https://www.cs.cmu.edu/~theorylunch/