Computational Complexity Theorist
Chicago
Joined July 2008
- Tweets6.4K
- Following389
- Followers7K
- Likes968
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
Interesting Precedence: In 1989 the AMS published a paper "Short proofs of two hypergeometric summation formulas of Karlsson" authored by Shalosh B. Ekhad, the nom de computer of Doron Zeilberger.
doi.org/10.1090/S0002-9939-1…
HT Evangelos Georgiadis
Noam Nisan once said to me that it is better to read a poorly written proof because you'll come out of it with a better understand than if the proof is well written. Now you get your chance.
blog.computationalcomplexity…
If you write a paper and AI is the main driver of the proof, that should go on the first page, mentioned in the abstract or as a footnote in the title and not just buried at the end of the paper. Otherwise you are claiming research that is not quite your own.
Avi Wigderson surveys the recently departed Michael Rabin's research
eccc.weizmann.ac.il/report/2…