Computational Complexity

My favorite quote about networking came from Jim Kurose. The Internet works so well because it doesn't have to. The IP and lower layer...

A few months ago in Oxford, Bernard Sufrin, an emeritus fellow, said he's looking to hire a student to implement LEAP (Logic Engine for ...

Michael Rabin passed away on April 14, 2026 at the age of 94.  (Scott Aaronson has also blogged about his passing, see   here .)  I had many...

At Oxford I focused my research and discussions on how we can use the tools of computational complexity to help us understand the power and ...

 Guest post from Peter Brass, Former NSF Theory director (though not affiliated with the NSF now) on the White House NSF budget for FY 2027....

I posted about using the Banach-Tarski Paradox(BT)  to explain the miracle of Loaves and Fishes (LF)  here . Darling says that whenever I fo...

Here are the solutions to the problems I posted last week . Problem 1 A language \(L\) is commutative if for all \(u\), \(v\) in \(L\...

I blogged about Pope Leo XIV  here . Pope Leo XIV has an undergraduate degree in mathematics. He saw my post and asked for my help with his ...

Occasionally I run into what I consider fun problems in complexity, that require just a little bit of out of the box thinking. They require ...

High table dinner at Magdalen My time in Oxford has come to an end and I head back to Chicago this week. I was a visiting Fellow at Magdalen...

 If I get an email offering me a $1000 for I DON"T KNOW SINCE  I ignore it and don't even bother looking for other signs it is a sc...

Gilles Brassard and Charlie Bennett Charlie Bennett and Gilles Brassard will receive the 2025 ACM Turing Award  for their work on the founda...

(If you live in Montgomery County Maryland OR if you care about Education, you MUST read this guest blog by Daniel Gottesman on Scott Aarons...

Turing Award winner and former Oxford professor  Tony Hoare passed away last Thursday at the age of 92. Hoare is famous for quicksort, ALGO...

In my graduate Ramsey Theory class I taught Kruskal's tree theorem (KTT) which was proven by Joe Kruskal in his PhD thesis in 1960.  (Sh...

In discussions of AI and Mathematics, the discussion often goes to mathematical proofs, such as the the  First Proof  challenge. So let'...

Goodhart's law :  When a measure becomes a target, it stops being a measure.    I was watching the show Masterminds where Ken Jennings i...

Last week I had the pleasure of meeting Alex Bellos in Oxford. Among other things Bellos writes the Guardian Monday puzzle column . He gave ...

A commenter on  this post  asked for me (or anyone) to solve the problem without AI: A,B,C,D,E are digits (the poster said A could be 0 but ...

Computer Science Professor Joseph Halpern passed away on Friday after a long battle with cancer. He was a leader in the mathematical reason...