Computational Complexity Theorist
Chicago
Joined July 2008
- Tweets6.4K
- Following389
- Followers7K
- Likes970
Lance Fortnow retweeted
In lieu of flowers, memorial contributions may be made to:
Johns Hopkins Alzheimer’s Disease Research Center Fund
alzresearch.org/giving/
Alzheimer’s Foundation of America Caregiver Resources
alzfdn.org/donate/
Photo Credit: Tommy Garcia
Impagliazzo, Paturi and Williams set up a site to discuss the ETH Refutation
Discussion Blog: ethdiscussion.blog/2026/10/2…
Paper Depository: drive.google.com/drive/folde…
Lance Fortnow retweeted
I lectured on the "ETH false" (#3SAT in subexponential time) result in my grad complexity class at CMU today.
Didn't have time in 80 mins to do the full proof, but I hope I got across the main plan, and some of the basic TCS ingredients going into it.
youtu.be/_HlQGMcQWhA
My blog post on the apparent death of the exponential-time hypothesis.
blog.computationalcomplexity…
I first heard about the ETH result from Emerson Redding, an "AI Reporter" asking for comments. Somehow that didn't bother me as it was honest up front, and was willing to connect me to a human editor if I desired.
My occasional reminder that the solution to P v NP is not around the corner. The claimed refutation to ETH doesn't reduce the running times of NP problems in general, such as 3-coloring or CNF-SAT with no bounds on the clause size. We still have no approach to settling P v NP.
Lance Fortnow retweeted
Here is a short and simplified proof of ETH is false.
My goal here is to obtain a simplified disproof of the basic statement of ETH, without optimizing log factors.
It is self-contained and easy-to-understand. I have added a worked example also.
Paper is on my homepage: shivakintali.github.io
PDF file: shivakintali.github.io/paper…
CC: @AlexKontorovich @__alpoge__ @jdlichtman
@stevenstrogatz @sahilsingla81 @MTHajiaghayi @AlgoSvensson @kenono691 @littmath @nasqret @PI010101 @wtgowers @MarcusduSautoy @DrEugeniaCheng @JSEllenberg @JohnDCook @JDHamkins @AxlerLinear @oveisgharan @ch_nira @rrwilliams @lreyzin @ChrisPeikert @fortnow @RadishHarmers @thomasfbloom @abhatt2 @mahdi_tcs_ @octonion @prz_chojecki @thegautamkamath @KWRegan
We are announcing three new discoveries in mathematics, computer science, and physics about harmonic analysis, complexity theory, and quantum field theory.
openai.com/index/building-sc…
OpenAI claims that the Exponential Time Hypothesis is false, solving 3SAT (even counting the number of solutions) in 2^{o(n)} time, with a Lean formalization of the proof.
Announcement: openai.com/index/building-sc…
Paper: github.com/openai/math/blob/…
1/2
Message from Russell Impagliazzo, Mohan Paturi and Ryan Williams about the ETH annoucement: docs.google.com/document/d/1…
"Our involvement should not be taken as certification of the claim. A result of this significance requires careful, independent scrutiny..."
2/2
Lance Fortnow retweeted
An internal model at OpenAI has produced a claimed refutation of ETH! Russell Impagliazzo, Mohan Paturi, and I have been asked to help organize an open and independent examination of this claim. 1/4
Bill looks at algorithms that are probably not optimal.
blog.computationalcomplexity…
Bill and I revive the vidcast to talk about the current moment. Enjoy!
youtu.be/ZYqLpb4PMXw?si=zY6n…
One of my readers calls me out on a prediction I made that I could be replaced as a teacher.
blog.computationalcomplexity…
Clip: share.gemini.google/5tG8fl89…
Danny Calegari gave a talk in the UChicago Math in the Age of AI Seminar about how he uses Claude to collaborate, visualize math, and create the slide deck from a single prompt. The best part of the talk was not the AI but Calegari’s own quotes.
1/6
“They say LLMs mirror yourself back to you. That’s flattering, I think they behave better.” The conversations keep track of mistakes and dead ends.
5/6
You can watch his whole talk at youtube.com/watch?v=jj7cEfnN…
6/6
Ruixiang Zhang told me about MathHelm, a non-profit site from mathematicians for mathematicians to discuss AI generated math papers.
mathhelm.org/about