Hilldale Lecture's Theory Seminar | UW-Madison Computer Sciences Dept.

Tuesday, October 17, 2017 -
11:00am to 12:30pm
CS 1240

Speaker Name: 

Prof. Richard Lipton

Speaker Institution: 

Georgia Institute of Technology

Cookies: 

Yes

Cookies Location: 

CS 1240

Description: 

Three Of My Favorite Open Problems

I will discuss some open problems that I have worked on forever. I think these problems should be solvable but progress is very limited. The first is essentially the halting problem for linear automata. It has been called a shame that we cannot prove it is either decidable or not. I will report on some partial results. The other two problems I will leave as a surprise, but they are both related to our P vs NP question.