DIMACS - Graduate Student Combinatorics Seminar

Title: Fun With PSPACE

Speaker: Nathan Fox, Rutgers University

Date: Wednesday, February 10, 2016 12:10pm

Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ


You're walking down the hallway of Hill Center. You pass a group of cool computer scientists. They are having a conversation about something called PSPACE. You think to yourself, "I wish I knew what PSPACE was so I could be as cool as them." Good news! In this talk we will define PSPACE and introduce a well-known PSPACE-complete problem. Then, we will use these concepts to prove that a much more fun problem is PSPACE-card, er, I mean PSPACE-hard. (Disclaimer: This talk will teach you about PSPACE, but it will not teach you how to use correct grammar in your thoughts.)

See: http://math.rutgers.edu/~klm296/GCS/index.html