Joint Computer Science Speaking Skills Talk / Theory Lunch Seminar

— 1:00pm

In Person - Gates Hillman 8102

BERNARDO SUBERCASEAUX , Ph.D. Student, Computer Science Department, Carnegie Mellon University

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:

Add event to Google
Add event to iCal