The Blog of Scott Aaronson

*Quantum computers are not known to be able*

to solve NP-complete problems in polynomial time,

and can be simulated classically with exponential slowdown.

to solve NP-complete problems in polynomial time,

and can be simulated classically with exponential slowdown.

Comment #1 May 24th, 2010 at 1:22 pm

Yes, Martin Gardner lightened our lives. He will be greatly missed.

Comment #2 May 24th, 2010 at 1:30 pm

I was fortunate to grow up while MG was writing Mathematical Games for Scientific American; I learned that math is fun. For me, it was a special event when MG would update us on the doings of Dr. Matrix, his lovely daughter Eva, and his occasional guide Rhee, who had but one tooth.

Comment #3 May 24th, 2010 at 8:24 pm

I can remember A.K. Dewdney’s “Computer Recreations” from SciAm. Reading these in class was more interesting than finding the real roots of polynomials of degree 2… I also remember “Mathematical Recreations” … when did Martin Gardner’s columns run?

Comment #4 May 25th, 2010 at 6:30 pm

Same for Walter Rudin, sadly.

Comment #5 May 25th, 2010 at 6:44 pm

Is Knuth the king?

Comment #6 May 25th, 2010 at 11:54 pm

Akhil,

Has Walter Rudin left us? What a brilliant guy. I have studied three of his books, and they are great; I will go up to the attic and dust them off.

I met Mary Ellen Rudin, Walter’s wife, after a lecture on topology. We had some laughs discussing laws imposed by the dairy industry in Ohio and Wisconsin. Back in the day, it was illegal to dye margarine yellow to make it look like butter.

Comment #7 May 26th, 2010 at 10:18 pm

I basically got into analysis from Rudin’s three textbooks (especially Real and Complex Analysis- that one is awesome), and if I do become an analyst, he’ll be a large part of the reason.

Comment #8 May 26th, 2010 at 11:23 pm

Speaking of Analysis,

The subject is nicely summarized by Littlewood’s three little principles:

1. Any continuous function is almost uniformly continuous.

2. Any measurable set is almost a finite union of open intervals.

3. Anything that converges almost converges uniformly.

All the (initially terrifying) crap about pushing around deltas and epsilons is just pinning down “almost” in any given case. Like recursion, once you get it, it’s easy. Then it is pure joy to read Rudin, Hewitt and Stromberg for real analysis, and the books of Einar Hille and Peter Henrici for complex analysis.

If you are a computer scientist, you have to read Knuth. It might no longer be cutting edge, but it is so scholarly and beautifully presented. BTW, don’t forget “Concrete Mathematics”. In Knuth’s books I find a good laugh (jokes, funny way of saying things, …) every couple pages. And I doubt if I get half of them!

Comment #9 May 27th, 2010 at 1:22 am

I have first encountered Martin Gardner’s writing in a little book published in Hungarian which contained “science fiction stories written by scientists” and back then I was a high school student already interested in Mathematics so I curiously read No-sided Professor and I was thrilled. I was envy of those who could read English that they have an author like him.

Walter Rudin’s Functional Analysis became one of the first books written in English which I tried to read and I was surprised that in spite of my limited knowledge of the language it was so clear that I could follow most of it. When I used Real and Complex later I was amazed.

I hope they knew that so many people were/are grateful for them.

Comment #10 May 27th, 2010 at 11:36 pm

The Scientific American site has a large tribute to MG:

http://www.scientificamerican.com/report.cfm?id=Martin%20Gardner,%201914-2010&sc=WR_20100527

Who would have guessed he was a religious fanatic in his youth?

BTW, many will be surprised to learn what journal Knuth’s first publication was in. Hint: MM.

Comment #11 June 3rd, 2010 at 12:08 pm

Since you are basically my go to guy for breaking down advances in quantum computation (and the limits thereof), and you have an uncanny ability to make things understandable and you have an enormous amount of credibility and knowledge on these issues, could you please make a blog post about this?

http://arstechnica.com/science/news/2010/06/magic-quantum-wand-does-not-vanish-hard-maths.ars

Is it all true? How does the reduction about different kind of quantum computers work? Etc, Etc. I am sure you can make it interesting. And I find it hard to believe that such a paper wouldn’t excite you, even if it turns out to be wrong.

Comment #12 June 4th, 2010 at 10:53 am

Yesterday Arnol’d passed too.

Comment #13 June 5th, 2010 at 11:54 am

Consider the following known-plaintext attack. We are given some

plaintexts P_1,…,P_{n-1} and ciphertexts C_1,…,C_{n-1}. We’re

also given a ciphertext C_n. We run through every key K. When we find

K such that E_K(P_i) = C_i for every i