Computational Complexity

Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch

Wednesday, August 27, 2025

The Logical Argument

›
This will be one of a series of posts that I've always wanted to write but I needed to wait until I was no longer an academic administra...
10 comments:
Saturday, August 23, 2025

Was the George Foreman Grill The Best Invention of the last 50 Years?

›
(This post was inspired by  George Foreman , who passed away March 21, 2025, at the age of 76.) About 10 years ago I asked my class What is ...
11 comments:
Wednesday, August 20, 2025

The Phone

›
I've heard this story from a few places. A father watches Back to the Future II with his kid. The 1989 movie view of 2015 looks entirel...
10 comments:
Saturday, August 16, 2025

A few more notes about Tom L

›
Tom Lehrer passed away on July 26, 2025, at the age of 97. I wrote a blog-obit  here . One of my readers read the post and went down a rabbi...
3 comments:
Wednesday, August 13, 2025

Total Pixel Space

›
Last month the New York Times highlighted some AI generated short movies, including Total Pixel Space , by Jacob Adler that gets philosophi...
Sunday, August 10, 2025

My Tom L post inspired a mathematical definition of Rabbithole

›
NICK: I read and enjoyed your blog post on Tom L (see  here ). I then spent 40 minutes down a rabbithole listening to his music on YouTube. ...
6 comments:
Thursday, August 07, 2025

AI and ...

›
AI and Vacation I'm back from my German vacation. This was my first AI vacation, by which I mean how I used AI to navigate a foreign cou...
15 comments:
Monday, August 04, 2025

Some thoughts on journals, refereeing, and the P vs NP problem

›
A guest post by Eric Allender prompted by an  (incorrect) P ≠ NP proof   recently published  in Springer Nature's Frontiers of Computer ...
92 comments:
Sunday, July 27, 2025

Tom Lehrer Passed Away at the Age of 97

›
Tom Lehrer passed away on Saturday July 26 at the age of 97. (For other obits see this collection of ten obits  here .) He worked in both of...
4 comments:
Thursday, July 24, 2025

Answer to my GROUP ONE/GROUP TWO Prez question

›
In a prior post I asked what criteria I used to place Prez and VP nominees since 1976 into two groups.  In the book  Abundance  I read that ...
5 comments:
Monday, July 21, 2025

Trevisan Prize- Deadline July 31 for Notification Intent, Aug 31 for nomination.

›
A new prize: The Trevisan Prize, in honor of Luca Trevisan, who died in 2024 (blog obit is  here , open problems column in his honor is  her...
Sunday, July 20, 2025

A Prez Question: Can AI do it? Can you? Can I?

›
 I am curious how AI or humans can do on the following question. I have listed out the nominees for Prez and VP (Vice Prez) since 1976 and p...
26 comments:
Wednesday, July 16, 2025

Turing, Wagner, Ruth

›
Douglas Hofstadter first published  Gödel, Escher, Bach: an Eternal Golden Braid  in 1979 and my then high school self tried, and failed, to...
5 comments:
Sunday, July 13, 2025

How much money did Francis Scott Key give to have a building named after him?

›
UMCP has a building named  The Francis Scott Key Building STUDENT: How much money did Francis Scott Key give to have a building named after ...
10 comments:
Wednesday, July 09, 2025

The Customers of the Academy

›
I had an epiphany reading an article in the Trenton Times when I lived in New Jersey at the turn of the century. The article interviewed com...
4 comments:
Sunday, July 06, 2025

The New Lower Bound on Busy Beaver of 6.

›
 We denote the busy beaver function by BB. BB(n) is the max time a Turing machine of size n takes to halt on the empty string. (A particular...
2 comments:
Wednesday, July 02, 2025

A Professor Again

›
A  new dean has taken my place, and I have returned to the professoriate at Illinois Tech, ending thirteen years in administration, six as ...
7 comments:
Sunday, June 29, 2025

Two high school students have a new proof of the Pythagorean Theorem / Pythag theorem older than thought

›
(I wrote this post a while back so its no longer NEW. More important--- if there has been a follow-up to the story that is not in my post, l...
6 comments:
Thursday, June 26, 2025

The Distribution of Prime Numbers: A Geometrical Perspective

›
Alberto Fraile and Daniel Fernández guest post on random walks generated by the distribution of prime numbers. In our recent papers, we expl...
7 comments:
Monday, June 23, 2025

If you do well in the UMCP HS Math Competition you may win $1,000,000

›
The Univ of  MD at College Park holds a HS Math Competition every year. At the reception for the winners Professor Larry Washington points t...
6 comments:
‹
›
Home
View web version
Powered by Blogger.