31
Malthusianisms
(See also: Umeshisms, Anthropicisms) Why, in real life, do we ever encounter hard instances of NP-complete problems? Because if it’s too easy to find a 10,000-mile TSP tour, we ask for a 9,0…
Scott Aaronson
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.
- Popular posts
- 50
- Total points
- 10,542
- HN comments
- 4,956
- Rank
- #73 personal
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
32
The Complete Idiot’s Guide to the Independence of the Continuum Hypothesis
A global pandemic, apocalyptic fires, and the possible descent of the US into violent anarchy three days from now can do strange things to the soul. Bertrand Russell—and if he’d done no…
33
Why Philosophers Should Care About Computational Complexity
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…
34
Quasi-Polynomial Algorithm for Graph Isomorphism
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…
35
Progress on longstanding open problems
For those who haven’t seen it: Aubrey de Grey, better known to the world as a radical life extension researcher, on Sunday posted a preprint on the arXiv claiming to prove that the chromatic …
36
The Scientific Case for P≠NP
Out there in the wider world—OK, OK, among Luboš Motl, and a few others who comment on this blog—there appears to be a widespread opinion that P≠NP is just “a fashionable dogma of…
37
Ten Signs a Claimed Mathematical Breakthrough is Wrong
Yesterday several people asked my opinion of a preprint claiming to solve the Graph Isomorphism problem in deterministic polynomial time. I responded: If I read all such papers, then I wouldn’t hav…
38
Time Travel (2006)
Last time we talked about free will, superintelligent predictors, and Dr. Evil planning to destroy the earth from his moon base. Today I'd like to talk about a more down-to-earth topic: time travel. The first point I have to make is one that Carl Sagan made: we're all time travelers—at the rate of one second per…
39
Insert D-Wave Post Here
In the two months since I last blogged, the US has continued its descent into madness. Yet even while so many certainties have proven ephemeral as the morning dew—the US’…
40
Intro to Quantum Information Science
Someone recently wrote that my blog is “too high on nerd whining content and too low on actual compsci content to be worth checking too regularly.” While that’s surely one of the…
41
Bell inequality violation finally done right
A few weeks ago, Hensen et al., of the Delft University of Technology and Barcelona, Spain, put out a paper reporting the first experiment that violates the Bell inequality in a way that closes off…
42
Scott Aaronson explains his $200k bet (8 Signs A Claimed P≠NP Proof Is Wrong)
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…
43
Tell President Obama to support the Federal Research Public Access Act
If you’re tired of blog posts about open science, sorry dude—but it feels great to be part a group of blogging nerds who, for once, are actually having a nonzero (and positive, I think!…
44
What Alan T. did for his PhD
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…
45
Why are amplitudes complex?
[By prior agreement, this post will be cross-posted on Microsoft’s Q# blog, even though it has nothing to do with the Q# programming language. It does, however, contain many examples th…
46
P vs. NP for Dummies
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…
47
Why I Am Not An Integrated Information Theorist (or, The Unconscious Expander)
Happy birthday to me! Recently, lots of people have been asking me what I think about IIT—no, not the Indian Institutes of Technology, but Integrated Information Theory, a widely-discussed &#…
48
Rosser’s Theorem via Turing machines
(Thanks to Amit Sahai for spurring me to write this post!) The Background We all remember Gödel’s First Incompleteness Theorem from kindergarten. This is the thing that, given a formal syste…
49
My visit to D-Wave: Beyond the roast-beef sandwich
Last week I was in Vancouver, to give talks at the University of British Columbia and at the American Association for the Advancement of Science annual meeting. As part of that visit, on Friday af…
50
PHYS771 Quantum Computing Since Democritus
University of Waterloo, Fall 2006 Tuesdays and Thursdays, 1:00-2:30pm BFG Building, 2nd floor seminar room (BFG2125)