Ken Regan Turned 61

Gödel’s Lost Letter and P=NP 2020-09-15

Happy birthday to Ken

Ken Regan is of course my partner on GLL. He is faculty in the computer science department at the University of Buffalo. His PhD was in 1986 from Oxford University and it was titled On the separation of complexity classes. He was the PhD student of Dominic Welsh who was a student of John Hammersley.

Today I would like to wish Ken a happy birthday.

He is now 61 years young. I hope you will join me and wish him many more birthdays. His age is special for many reasons:

  • It is a twin prime.
  • It is equal to {5^{2} + 6^{2}}.
  • It is the ninth Mersenne prime: {2^{61} - 1 = 2,305,843,009,213,693,951}.

There are three big I’s in his life. Let’s talk about two of them.

Interest in Cricket

Ken loves sports in general and especially cricket. Last Sunday he told me he watched his Bills win their first NFL game while he watched a cricket match. I have no idea how cricket works, but here is Ken’s explanation: Are Cricket and Baseball sister games?

  • In a baseball game you see pitchers on the field. In a cricket match you see fielders on the pitch.
  • In baseball, a bad delivery is called a “Ball”. In cricket, it’s a “No Ball”.
  • In baseball, if a batter carries his bat, he’s out. In cricket, the batsmen always carry their bat, and an opening batsman who “carries his bat” is never out.
  • In baseball, an innings is called a half-inning. In cricket, an inning is called an innings.
  • In baseball, a batter hit by a pitched ball gets a free pass to First Base. In cricket, such a batter can be Out Leg Before Wicket.
  • In baseball, if a ball is caught over the boundary, “yer out!” In cricket, you score 6 runs.
  • In baseball, when a batter “walks”, he gets a free pass to first and is not out. In cricket, it means the batsman declares himself out before the umpire has a chance to make the call. This classic show of sportsmanship is considered unsportsmanlike in baseball.

    Interest in Chess

    When the chess world wants to know if someone has cheated, they call Ken. He is an international chess master, and has worked on stopping cheating for years. It is important these days, since most tournaments are now online. And cheating is easier when no one is directly able to watch you. Ken is busy.

    Let’s look at the cheating problem. Suppose that Alice and Bob are playing an online game of chess. Alice makes her own moves, but she wonders if Bob could be cheating. He could be using advice from another “player”, Sally. There are several points:

    1. Sally is a stronger player than anyone—she can easily beat Alice and Bob.
    2. Sally not only says “here is my move”—she will sometimes give several good moves.
    3. Sally is a program that is deterministic—given a position she gives the same answer.The issue for Ken is: When Alice played Bob did Bob make the moves or did he consult Sally?

    There are many complexities:

    1. What if Bob agreed with all Sally’s moves? Then he certainly did cheat.
    2. What if Bob was just lucky and played above his strength? Then he did not cheat.
    3. What if Bob used Sally for some positions but not others? Then he did cheat, but it may be hard to be sure.
    4. And so on.

    What Ken has done is create both a theory and programs to determine whether Bob did indeed cheat. I find the general problem of telling if one cheats online at chess to be fascinating. See us before for more details and also see this.

    Open Problems

    Ken is one of the nicest people I know. Hope he has many more birthdays and many more twin primes.