Computational Complexity
blog.computationalcomplexity.org
Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
- Posts
- 3,343 from 23 Aug 2002 to 28 Oct 2026
- Posting
- weekly (97 in the last year)
- Kind
- personal blog
- Feed
- https://blog.computationalcomplexity.org/feeds/posts/default
Latest
October 2026
- The Exponential Time Refutation
- When is it plausible that a result is optimal?
- Reading Messy Proofs
- AI, Math, the document-drop. Non-Tech Thoughts
- Complexity and Lean
- Conjectures that I thought would not be proved in my lifetime....were
- Open No More
- How many humans does it take to make tech seem human? Do you want to be one of them?
September 2026
- Does Programming Help You Understand Complexity?
- What is the point of AI-disclosure?
- The New STOC Rules for the AI Era
- I don't care about majors, minors, or honors programs. Do you?
- AI and Manufacturing Redux
- Math, AI, and the Navier-Stokes Equations
- Navier-Stokes and Lean
- Richard Stearns (1936-2026)
- What is a Computer?
August 2026
- Claude and Colorblind Questions
- The Calculator Transition
- Centaur Math
- IIT is the canary in the coalmine (Do our younger readers know what that means? Do we have younger readers?)
- Unexpected Unemployment
- Math Concepts With Funny Names
- A problematic category on Jeopardy Raises a Good Question
July 2026
- Would Erdos have been happy with the resolution of the Erdos Unit Distance Problem? How to find out?
- Complexity Class of the Week: \(L_2^P\)
- Bipartite Perfect Matching in Deterministic NC
- Herman Chernoff (1923-2026)
- 2... 1/2 THEN 3... 1/6 THEN 5 ....1/15 and so on. And So On?
- Wither/Whither the ACM
- Extreme cases of clickbait!
- The True Method
June 2026
- Guest Post by Peter Brass on the new NSF guidelines
- The Zone
- The New Result on Off-diagonal Ramsey Numbers
- The Tech of Silk Road
- mnemonic devices and pangrams that could be real sentences
- Respect the P v NP Problem
- Humans Solve Erdos Problem!!
- The Industrialization of Academic Research
- Odd Scenarios about Research Claims and Authorships
May 2026
- Authorship in the AI Age
- Two Erdős Problems on Points in the Plane and AI
- Range Avoidance
- Scott Aaronson wins Trevisan Award? Prize? Medal? Statue?
- Prediction Markets Redux
- Searches Are Weird! No they're not! Bad coding style?
- When do we know someone has died
- A few notes on Michael Rabin
April 2026
- Because It Doesn't Have To
- LEAPing into the Future of Coding
- Michael Rabin Passed Away on April 14, 2026, at the age of 94
- Machine Learning and Complexity
- Guest Post from Peter Brass, Former NSF Theory Director, on the NSF budget.
- Afterthoughs on Banach Tarski and the Miracle of loaves and Fishes
- Fun Little Solutions
- I helped the Pope's with his latest Encyclical (His Math Background Helped)
March 2026
- Fun Little Problems
- My Oxford Term
- A $100 gift card could be legit. A $1000 is obviously a Scam. What should scammers do?
- Bennett and Brassard Win the Turing Award
- For \(R^3\) the problem is open. That's too bad. We live in \(R^3\)
- Tony Hoare (1934-2026)
- How does AI do on Baseball-Brothers-Pitchers
- The Purpose of Proofs
- Goodhart's law: Ken Jennings and Types of Knowledge
February 2026
- A Probability Challenge
- ChatGPT gets an easy math problem wrong (I got it right). How is that possible?
- Joe Halpern (1953-2026)
- Assigning Open Problems in Class
- The Future of Mathematics and Mathematicians
- I used to think historians in the future will have too much to work with. I could be wrong
- Sampling the Oxford CS Library
- Before the ChatGPT-HW debate there were other ``If students use X to do their HW'' debates
January 2026
- The Fighting Temeraire (Re)visited
- Online Talks on Accessible Theorems!
- Community
- What to do about students using ChatGPT to do their homework?
- Rational Functions Solved!
- Is `smells like' commutative?
- Computational Depth
- AI and Research Papers
- The Betty White Award for 2025
December 2025
- Complexity Year in Review
- A Place Away From Tech
- Weird Al vs Weird AI
- Learning the Mathematical Process
- Tom Stoppard 1937-2025
- Finding Papers Before the Web
- Does ChatGPT really help programmers?
November 2025
- The Little Theorems
- Factoring Carmichael Numbers
- Test of Time Awards: A Good Idea but ....
- The Future of Teaching Assistants
- A Presidential Trivia Question, how I tried to solve it
- The Complexity Argument for Capitalism
- Did Euclid exist? Is it okay to quote people that did not exist?
October 2025
- AI and the Power of Nonuniform Circuits
- Bill's Bad Advice
- AI and Intro Theory
- Sept 16, 2025 was Pythagorean Day
- Fall Jobs Post 2025
- The Most Common Name in the World is Not Charles Lin. But It Seems That Way To Me.
- Big Bots Don't Cry
- If you use AI in your work do you brag about it or hide it?
- Computers Don't Want
September 2025
- Clyde Kruskal talks about his Father Martin on Martin's 100th birthday
- Self-Driving Cars
- We can find more papers on the web than we used to. Are we reading them?
- What is "PhD-Level Intelligence"?
- ``I'm on vacation so I won't be checking email'' will sound funny soon. Maybe it already does.
- Is the Prob Method `Just Counting'- I say no and HELL NO
- A Restless Soul
- Guest Post on Why Coding Style is Important
August 2025
- The Logical Argument
- Was the George Foreman Grill The Best Invention of the last 50 Years?
- The Phone
- A few more notes about Tom L
- Total Pixel Space
- My Tom L post inspired a mathematical definition of Rabbithole
- AI and ...
- Some thoughts on journals, refereeing, and the P vs NP problem
July 2025
- Tom Lehrer Passed Away at the Age of 97
- Answer to my GROUP ONE/GROUP TWO Prez question
- Trevisan Prize- Deadline July 31 for Notification Intent, Aug 31 for nomination.
- A Prez Question: Can AI do it? Can you? Can I?
- Turing, Wagner, Ruth
- How much money did Francis Scott Key give to have a building named after him?
- The Customers of the Academy
- The New Lower Bound on Busy Beaver of 6.
- A Professor Again
June 2025
- Two high school students have a new proof of the Pythagorean Theorem / Pythag theorem older than thought
- The Distribution of Prime Numbers: A Geometrical Perspective
- If you do well in the UMCP HS Math Competition you may win $1,000,000
- Fulbright Memories
- Lance never thought he would see a Pope who roots for the same team as him. And now...
- Defending Theory
- The New Godel Prize Winner Tastes Great and is Less Filling
- Rules vs Standards
- Complexity theory of hand-calculations
May 2025
- The Hilltop Story
- Some are Mathematicians, some are Carpenters' Wives, Some are Popes.
- The Blog of Record
- Is Satire Dangerous in the AI-Age?
- A Bittersweet Anniversary
- Random Thought on the New Pope (the actual New Pope, not the TV series). He was a math major!
- Using AI for Reviews
- My response to Scott's least controversal post ever!
April 2025
Every year
2026 832025 982024 1022023 922022 772021 892020 762019 842018 1002017 1012016 1012015 1032014 1112013 1082012 1322011 1342010 1912009 2492008 2532007 1592006 2382005 2372004 2002003 1492002 76