Tech News
← Home  ·  All topics

Exponential Time Hypothesis

1 GoKawiil brief on this topic

OpenAI claims three math/CS proofs, including disproof of ETH

OpenAI posted results to GitHub including a proof extending Sogge's local smoothing for waves to all dimensions above two, which also yields related Kakeya and Stein restriction estimates. It also released a paper claiming a deterministic subexponential-time, polynomial-space algorithm for counting satisfying assignments of fixed-width CNF formulas, which for 3-SAT would refute the Exponential Time Hypothesis. A group led by Russell Impagliazzo, Ramamohan Paturi, and Ryan Williams will review the ETH claim, and OpenAI released materials immediately at that group's request.