I'm Schlumberger Centennial Chair of Computer Science at The University of Texas at Austin , and director of its Quantum Information Center . My research interests center around the capabilities and limits of quantum computers, and computational complexity theory more generally.
Visit scottaaronson.com → On Hacker News May 2009 – Jan 2021
Science & Space 26Math & Algorithms 26Society, Policy & Culture 15Life, Learning & Writing 9Software Engineering 8AI & Machine Learning 7
The Sensitivity Conjecture, which I blogged about here, says that, for every Boolean function f:{0,1}n→{0,1}, the sensitivity of f—that is, the maximum, over all 2n input strings x∈{0,1}n, of…
[This essay in Spanish] [This essay in French] [This essay in Chinese] In an old joke, two noblemen vie to name the bigger number. The first, after ruminating for hours, triumphantly announces "Eighty-three!" The second, mightily impressed, replies "You win." A biggest number contest is clearly pointless when the…
For twenty years, the fastest known algorithm to multiply two n-by-n matrices, due to Coppersmith and Winograd, took a leisurely O(n2.376) steps. Last year, though, in his PhD thesis, Andrew Stot…
Update (August 11, 2011): Thanks to everyone who offered useful feedback! I uploaded a slightly-revised version, adding a “note of humility” to the introduction, correcting the footnot…
Update (Dec. 14): The long wait is over! Here’s Laci’s paper on the arXiv. So far, I’ve read it only deeply enough to note that it contains the following sentence: A group G ≤ S…
As of this writing, Vinay Deolalikar still hasn’t retracted his P≠NP claim, but a clear consensus has emerged that the proof, as it stands, is fatally flawed. The first reason is that weR…
We’ve all been there before: by the time you start graduate school in Princeton, you’ve already invented the Turing machine, pioneered the concept of computational universality, and pro…
A reader named Darren commented on my last post: I have this feeling that this whole P and NP thing is not only a profound problem that needs solving, but something that can be infinitely curious t…