Department of

# Mathematics

Seminar Calendar
for events the day of Friday, February 5, 2021.

.
events for the
events containing

Questions regarding events or the calendar should be directed to Tori Corkery.
     January 2021          February 2021            March 2021
Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
1  2       1  2  3  4  5  6       1  2  3  4  5  6
3  4  5  6  7  8  9    7  8  9 10 11 12 13    7  8  9 10 11 12 13
10 11 12 13 14 15 16   14 15 16 17 18 19 20   14 15 16 17 18 19 20
17 18 19 20 21 22 23   21 22 23 24 25 26 27   21 22 23 24 25 26 27
24 25 26 27 28 29 30   28                     28 29 30 31
31


Friday, February 5, 2021

4:00 pm in Zoom,Friday, February 5, 2021

#### Satisfiability: Why some problems are easy, while others are hard

###### Vaibhav Karve (UIUC)

Abstract: I will introduce a 50-year-old problem called Boolean Satisfiability (or simply SAT) and I will explain why we should care about it. We will explore how an abstract-looking problem can end up being connected to circuits, airline scheduling, Rubiks cubes, chess, video games, and travelling salesmen. I will explain how small SAT are easy and how big SAT can be hard -- and how we quantify the hardness of a problem. By the end of the talk, we will have learned some computer science as well.