CMPSC 292A The Exponential Time Hypothesis is False

On October 26th 2026 OpenAI published an algorithm for n-variable k-SAT that runs in time approximately 2^O(n/sqrt{log n}) time. Assuming that this is correct (it likely is) this disproves the "Exponential Time Hypothesis", and amounts to nothing less than a revolution and paradigm shift in a large part of theoretical computer science. In this course we will study the Exponential Time Hypothesis, how it has been used, the published disproof of the ETH, and (assuming it is correct) start picking up the pieces from the fallout. 

Once the quarter starts, instructor approval is required to maintain enrollment in the course.