Scott, I’d like to know if you’ve ever thought about writing a book on complexity, especially an introductory one.

I’ve done more than think about it! Within a year or so, Cambridge University Press will be publishing a book based on my Quantum Computing Since Democritus lectures.

What about quantum complexity, QIS… What are good introductory books?

Sorry for the long delay! I recommend David Mermin’s “Quantum Computer Science” for complete beginners, and then the Nielsen & Chuang book.

The Feynman Lectures are … well, the Feynman Lectures, among the greatest physics books ever written. Just don’t expect to learn about quantum computing / information from them.

What do you think of K. Mulmuley’s (of UChicago) approach to P vs. NP via GCT?

I’m planning a whole blog post about it—stay tuned!

Scott, would you be kind enough to provide a “Shor, I’ll do it”-like demonstration of how to reduce an instance of a travelling salesman problem into an instance of a graph coloring problem? Please, it’s my birthday!

Happy birthday!! But on your next birthday, could you ask for something less wince-inducing?

Alright, alright, here’s an outline:

First reduce Traveling Salesman to SAT. (That this is doable follows immediately from the Cook-Levin Theorem.)

Next reduce SAT to 3SAT. (That’s a simple reduction, as pointed out in Cook’s original paper.)

Finally reduce 3SAT to coloring. (That’s a standard gadget construction—it’s even covered in my GITCS notes, linked to on the sidebar of this blog.)

For more read Garey & Johnson, or google for lecture notes about NP-completeness until you find ones that you like.

So Scott, any opinion on this?

Sorry, I don’t like questions that require reading the questioner’s paper even to understand what’s being asked.

(Specifically, I don’t understand what a “random field” is in your context—is it possible to give a completely discrete explanation, involving only bits and qubits?)

Can you extend Terry Tao’s wonderful expository relativization metaphor to a wonderful expository metaphor for algebrization?

I’m a huge fan of Tao’s blog, but to be honest, this particular metaphor seems to take something simple and make it complicated. If it works for you, great—but I’m probably not the right person to extend it to algebrization.

In particular, do you personally think that it is possible to teach oneself and do something without interacting with the bright minds (which I have been doing)?

Sure, but interacting with “the bright minds” helps, so you should seek them out whenever feasible.