«
»

Ask Me Anything

Update (8/16): Phew! By my count, I’ve answered 139 questions over the past few days. Thanks so much to everyone for submitting them, and please don’t submit any more!

Incidentally, to those of you who complain (correctly) that I no longer update this blog enough, there’s a simple solution that should carry you through at least the next year.  Namely, just read a few “Ask Me Anything” answers every week!  To help you with that, I’ve compiled the following abridged table of contents to my uninformed spoutings:

 

Update: Thanks for the many, many, many great questions!  To keep things slightly under control, I’ll be fielding questions that are asked before 9PM EST tonight.

Also, sorry my blog went down for an hour!  I always count on Bluehost to not be there when I need it.

Alright, I put it off for most of the summer, but I guess it’s as good a time as any, now that (a) I’m finally done philosophizing for a while and (b) my wife Dana is away at a workshop, her civilizing and nerdiness-moderating influences temporarily absent.

So, by popular demand, and as promised a couple months ago, for the next 24 hours (with intermittent sleep breaks), I’ll once again be fielding any and all questions in the comments section.  Four simple ground rules:

  1. No multi-part questions: one question per comment and three total per person.
  2. While you can ask anything, if it’s too hostile, nosy, or irritating I might not answer it…
  3. I’ll only answer the first three questions about academic career advice (since in previous Ask Me Anything posts, that topic tended to drown out everything else).
  4. No questions that require me to read an article, watch a video, etc.
Email, RSS Follow

This entry was posted on Saturday, August 13th, 2011 at 11:25 pm and is filed under Ask Me Anything, Nerd Interest. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

281 Responses to “Ask Me Anything”

  1. Jiav Says:
    Comment #1 August 13th, 2011 at 11:51 pm

    In 1982 CH Bennett made a very interesting connexion between information and energy, noticing that “the essential irreversible step, which prevents [Maxwell’s] demon from breaking the second law, is not the making of a measurement […] but rather the logically irreversible act of erasing the record of one measurement to make room for the next”.

    1-Do you agree with this view?

    2- Can we infer from this view that the second law forbid the (physical) existence of oracle for data compression?

    3- Can we extend the idea to show that Closed Timelike Curves (P=PSPACE) or the collapse of the polynomial hierarchy (either P=NP or higher) would implicate free energy?

  2. Carl Says:
    Comment #2 August 14th, 2011 at 12:07 am

    As a philosophy grad student with an interest in CS, what should I be reading (besides your last paper)/where should I try to get published?

  3. Scott Says:
    Comment #3 August 14th, 2011 at 12:09 am

    Jiav #1:

    1 – Yes

    2 – I’m not sure what an “oracle for data compression” means—is it just an oracle that given a string x, returns (say) the smallest Turing machine that outputs x? If so, then I confess that I don’t see how one would use such an oracle to violate the Second Law. Maybe you or someone else could fill in the argument for me.

    3 – A few years ago, Seth Lloyd said he had an argument showing that if P=NP then one could violate the Second Law. But the argument was very sketchy, and I couldn’t follow it. I don’t know whether he or anyone else has worked out the details since then.

    It would certainly surprise me if starting from a computational assumption, you could build a free-energy machine! An obvious difficulty is that, even if a Maxwell Demon can solve NEXP-complete problems instantaneously, it still needs knowledge about the external universe—e.g., the locations of the gas particles. And despite its computational superpowers, it might never know enough about the initial state of the universe to calculate what it needs. Thus the obstacles to a Maxwell Demon seem information-theoretic rather than computational.

  4. Henry Y Says:
    Comment #4 August 14th, 2011 at 12:16 am

    What’s your crystal ball guess for the status of theoretical computer science vs “traditional mathematics” in 2100? Will thinking about Turing Machines or BQP lead to deep/major advances in algebraic geometry, or algebra, or analysis?

    I.e. will the mathematical community have recognized TCS as equally important to the development of mathematics as algebra or analysis are?

  5. LonePeep Says:
    Comment #5 August 14th, 2011 at 12:16 am

    Are there any situations under which it is impossible to simulate Newtonian/classical physics in polynomial time?

  6. oligogal-c Says:
    Comment #6 August 14th, 2011 at 12:17 am

    What are your comments on possibility of “NP in BQP”, i.e. if it is true that NP complete problems can be solved on quantum compute and someone shows it, what would be the implications for community and value of such result?

  7. Scott Says:
    Comment #7 August 14th, 2011 at 12:18 am

    Carl #2: Glad you’re interested! You could start with some of the 136 references in my essay. For example:

    – any modern complexity textbook (e.g., Moore and Mertens or Arora and Barak)
    – Ronald de Wolf’s Masters thesis
    – this paper on the Turing Test by Stuart Shieber

    Of course CS theory is a big field (to say nothing of the rest of CS) and it will strongly depend on what you’re interested in.

    I really don’t know much about where to publish papers on philosophy and CS theory, but when I was doing research for my essay, I found stuff in journals like Minds and Machines and Nous, as well as various book collections.

  8. paulia Says:
    Comment #8 August 14th, 2011 at 12:23 am

    Do you believe in transhumanism: what does it have to do with quantum computers, and what do you think of theory expressed in Alex Jons documentary ENDGAME (http://video.google.com/videoplay?docid=1070329053600562261) that transhumanism is for chosen few, while others will be opressed. Who should decide who gets to live forever and who lives a short life of a slave

  9. Lauri Says:
    Comment #9 August 14th, 2011 at 12:26 am

    Could you please compare your experiences in the MIT and Berkeley math/CS departments? (I’m studying at Cal this fall, so don’t count it as a career advice Q because I have no intention of going to MIT…yet).

  10. Scott Says:
    Comment #10 August 14th, 2011 at 12:36 am

    Henry Y #4:

    Unfortunately, my crystal ball is hazy even about rather more “basic” questions, like whether there will be a nuclear war by 2100, or whether the planet will still be able to support civilization in anything like the form we know it today. How the mathematicians (if there still are any) will feel about TCS is sort of a lower-order bit. 🙂

    For whatever it’s worth, though, I think TCS can spur important advances in pure math, and indeed that it’s already doing so—not in the sense that you’d prove a lemma about BQP on the way to an algebraic geometry theorem, but in the sense that TCS is an unbelievably rich source of mathematical problems and motivation, probably just as rich as theoretical physics has been. So sure, I’m optimistic about the mathematicians continuing to like us, for as long as we and they continue to exist!

  11. Caleb Wherry Says:
    Comment #11 August 14th, 2011 at 12:49 am

    How much would you pay for D-Wave’s “D-Wave One” system?

  12. Scott Says:
    Comment #12 August 14th, 2011 at 12:59 am

    paulia #6: For my general thoughts about transhumanism, see my post The Singularity Is Far.

    Summary: I’m all for improving the human condition by whatever means available (including genetic engineering of babies, brain-computer interfaces, radical life extension … you name it!). Furthermore, I hope and expect that at least some of these things will be realized in my lifetime. On the other hand, I also suspect that many of the transhumanists’ wilder technological projections might be too optimistic by several orders of magnitude—their habit of handwaving away engineering difficulties like a 1950s AI proponent does not inspire confidence. I also think that, even assuming one supports the transhumanists’ goals, the human race has many less glamorous and more immediate problems that we might need to solve first.

    Quantum computing is downright tame compared to most of the stuff the transhumanists want! 🙂 In general, I’d say QC could plausibly contribute to many of their goals (for example, quantum simulation could help a lot with the design of nanomaterials), but it’s neither necessary nor sufficient.

    No fair asking a question that requires me to read an article or watch a video! (I’ll add that rule to the post.)

    In general, though, opposing any new technology on the ground that “it will only be for the chosen few” seems asinine to me. You could have made precisely the same argument about radio, computers, air travel, antibiotics: what about the gap between the “haves” who could afford these things and the “have nots”? Eventually, of course, the prices of all of them came down to the point where billions of people could afford them. And if, sadly, there are still other billions of people who can’t afford them, do you think that’s a reason why these existing technologies should be banned?

  13. Anonymous Says:
    Comment #13 August 14th, 2011 at 1:03 am

    1. Do you sincerely believe that P captures feasible computations?

    2. What is the most complex mathematical objects that you are confident that they have objective reality (and questions about them have a answer)? e.g. sets in arithmetic hierarchy, sets in analytical hierarchy, all subsets of real numbers (which IMO would imply that you believe that CH is either true or false)?

    3. Which field of CS do you like most (putting aside the areas you work in, i.e. complexity and quantum computability)?

    4. Who are your top favorite 5 philosophers?

  14. Fring Says:
    Comment #14 August 14th, 2011 at 1:07 am

    Given the state of the economy, does solving a major problem in TCS give you a chance to get academic job in the field if you are from another field?

  15. Robert Says:
    Comment #15 August 14th, 2011 at 1:07 am

    Should D-Wave be taken seriously?

  16. Scott Says:
    Comment #16 August 14th, 2011 at 1:17 am

    LonePeep #5:

    Are there any situations under which it is impossible to simulate Newtonian/classical physics in polynomial time?

    There are some results (I don’t remember a reference offhand—does anyone?) suggesting that simulating Newtonian physics could even be uncomputable! The basic idea is that, if (for example) you could get a collection of point masses to move around under gravitational influence with speeds that asymptotically diverge, then you could use them to solve the halting problem in finite time.

    Now, I shouldn’t even need to add (but I do) that this sort of result is of mathematical interest only, not physical interest. And the reason is that Newtonian mechanics is false! What little we know today about quantum mechanics and gravity strongly indicates that time intervals shorter than the Planck time (~10-43 seconds) don’t even make physical sense. And the specific “hypercomputing” proposal that I sketched above even runs into problems long before that—e.g., it contradicts special relativity.

  17. Scott Says:
    Comment #17 August 14th, 2011 at 1:24 am

    oligogal-c #6:

    What are your comments on possibility of “NP in BQP”…

    We’ve discussed that many times on this blog; try searching the archives! Or watch my Buhl lecture, or try almost any of my other popular-level talks…

    Briefly, I think NP⊆BQP would be a scientific revolution, almost as great as P=NP. It would certainly justify a “Manhattan Project” aimed at building a scalable quantum computer. Unfortunately, like most quantum computing theorists, I currently see no good reasons to think NP⊆BQP should hold.

  18. dt Says:
    Comment #18 August 14th, 2011 at 1:25 am

    How hard can problems in P get?

    Among problems in P, are there any cool qualitative differences known or conjectured between problems that can’t be solved except in O(n) time, problems that can’t be solved except in O(n^2) time, problems that can’t be solved except in O(n^99) time, problems that can’t be solved except in O(n^99.44) time and so on?

  19. Scott Says:
    Comment #19 August 14th, 2011 at 1:32 am

    Lauri #9:

    Could you please compare your experiences in the MIT and Berkeley math/CS departments?

    It’s almost impossible for me to compare, for the simple reason that I was a grad student at Berkeley and then faculty at MIT. I think they’re both wonderful departments (the EECS departments, that is, which are the ones I know firsthand (not that the math departments aren’t wonderful too)). Berkeley has much better weather and wider availability of fruit smoothies, but MIT has less red tape and Boston right across the river.

  20. Scott Says:
    Comment #20 August 14th, 2011 at 1:33 am

    Caleb Wherry #11:

    How much would you pay for D-Wave’s “D-Wave One” system?

    I hereby offer $200 for one (provided the installation and setup—presumably right outside my office—are done for free).

  21. Scott Says:
    Comment #21 August 14th, 2011 at 2:02 am

    Anonymous #13:

    1. Do you sincerely believe that P captures feasible computations?

    Yeah, I think it’s a pretty good model (of course BQP is a better model, if you want to take into account our best current understanding of physics). Obviously, that doesn’t mean I wouldn’t prefer a 1.0000001n algorithm to an n10000 one in practice. See my philosophy essay for more.

    2. What is the most complex mathematical objects that you are confident that they have objective reality (and questions about them have a answer)? e.g. sets in arithmetic hierarchy, sets in analytical hierarchy, all subsets of real numbers (which IMO would imply that you believe that CH is either true or false)?

    Great question!

    But I prefer to talk about the truth or falsehood of statements, rather than the reality of objects—I have an easier time understanding what the former means.

    So, modifying the question with your kind indulgence, I’m gonna have to go with statements in the analytic hierarchy. Above that, my intuition gets progressively weaker—and by the time you reach CH, I have no intuition whatsoever that it should have an objective truth-value independent of its provability in some formal system.

    In the other direction, I think one can sanely question (though I wouldn’t) whether all statements in the analytic hierarchy have objective truth-values. On the other hand, if you question whether arithmetical statements have objective truth-values, then I think you’re caught in an infinite regress! At that point you might as well reject modus ponens and 1+1=2.

    3. Which field of CS do you like most (putting aside the areas you work in, i.e. complexity and quantum computability)?

    Someone asked that in a previous Ask Me Anything. AI, applied computer security, and computational biology are all areas that I cheerlead from the sidelines.

    4. Who are your top favorite 5 philosophers?

    Dude, the rule was three questions! But alright, since this is my favorite question so far…

    1. Bertrand Russell
    2. Democritus
    3. David Hume
    4. Spinoza
    5. John Stuart Mill

    (Among living philosophers: Daniel Dennett, David Chalmers, Nick Bostrom, Rebecca Goldstein…)

  22. Scott Says:
    Comment #22 August 14th, 2011 at 2:08 am

    Fring #14:

    Given the state of the economy, does solving a major problem in TCS give you a chance to get academic job in the field if you are from another field?

    Uhh, I guess it depends what you mean by “major.” While the job market is tight, if you prove P≠NP (or even NEXP⊄P/poly) I’m sure you can find a good job, regardless of which field you’re from.

  23. Scott Says:
    Comment #23 August 14th, 2011 at 2:14 am

    Robert #15:

    Should D-Wave be taken seriously?

    Should your question be taken seriously? 🙂 Given how much blog-ink I’ve already spilled on this subject?

    Certainly there are people at D-Wave who are doing good science. And we don’t know what they’ll accomplish in the future. As for their marketing claims about what they’ve already done, see my previous 10500 posts.

  24. Grad Student Says:
    Comment #24 August 14th, 2011 at 2:16 am

    What do you think of the (claims of) a higher education bubble in the US? If you think it exists, what do you think should be done about it? Should young people think twice before they go to college?

  25. Scott Says:
    Comment #25 August 14th, 2011 at 2:22 am

    dt #18:

    How hard can problems in P get?

    By the Time Hierarchy Theorem, for every k there are problems in P that require nk time.

    Of course, that still leaves the question of whether there are natural problems with huge polynomial complexities. Within the theory of parameterized complexity, one frequently encounters problems that (under plausible conjectures) require nΩ(k) time, where k is some parameter of the input other than its length (e.g., tree-width, the number of vertices in a clique you’re trying to find…). But I’m not sure whether those examples count.

    I don’t know of any “natural” problem (not involving large numbers in its statement) that’s known or even conjectured to require (say) n1000 time. Whether such problems exist is of course an extremely interesting question. Though note that, if such problems did exist, then the only way we’d be able to prove it in our current state of knowledge would be via a reduction to the Time Hierarchy Theorem.

  26. Anonymous Says:
    Comment #26 August 14th, 2011 at 2:30 am

    Thanks Scott.

    I could guess Russell and Democritus, might have guessed Mill and Hume also , but not Spinoza. I have to check living ones.

    ps: the world would become a very boring place if the rules were not broken from time to time. 😉

  27. Robert Says:
    Comment #27 August 14th, 2011 at 2:36 am

    Hahahaha, duly noted. Thanks Scott

  28. Plato Says:
    Comment #28 August 14th, 2011 at 2:40 am

    I presume we all agree that the western world’s economy isn’t at its best and it’s losing to China. What do you think about the status of science in the future? Are the best postgrad students going to go to the University of Nanjing, instead of MIT? Are American universities going to be less productive? Is this even something to be worried about?

  29. madhatter Says:
    Comment #29 August 14th, 2011 at 2:53 am

    Scott: I don’t understand the last sentence of your comment #25. Is there any reason to rule out a natural proof (in the sense of Razborov-Rudich) of an n^1000 lower bound for a problem?

  30. Scott Says:
    Comment #30 August 14th, 2011 at 3:01 am

    Grad Student #24:

    What do you think of the (claims of) a higher education bubble in the US?

    Since people don’t buy and sell shares in Harvard or Penn State, what exactly would a higher education bubble mean? Would it mean that high school students would decide en masse to stop going to college? If so, then I consider that unlikely for the foreseeable future. It’s true that the majority of college students might not care too much about what they’re learning (or not learning), but that’s always been the case! People have always gone to college for a variety of reasons:

    (1) Getting credentialed as someone smart.
    (2) The “social experience” (i.e., keg parties and getting laid).
    (3) Not letting their parents down.
    (4) Having an excuse to live away from home.
    (5) Doing what all their friends are doing.
    (6) Making contacts.
    (7) Putting off a decision about what to do with their lives.

    Now, looking through these reasons, many of them do seem indicative of a bubble: they only have force because most people believe they do. On the other hand, if this is a bubble, then it’s a bubble that’s stayed inflated since at least WWII!

    Should young people think twice before they go to college?

    I’ve always thought they should! Though note that, if you want to become a software billionaire, the historically-validated strategy is to go to college for one year, then drop out after you’ve made some crucial contacts.

  31. dan Says:
    Comment #31 August 14th, 2011 at 3:14 am

    1. Where do your good new ideas come from? (i.e., what is your creative process? )

    2. What is your process for deciding on which ideas to allocate time to?

    3. Would you ever (realistically) leave academia? If yes, what would it take? If no, why not?

  32. Scott Says:
    Comment #32 August 14th, 2011 at 3:20 am

    Plato #28:

    Are the best postgrad students going to go to the University of Nanjing, instead of MIT?

    Everyone keeps saying that, yet it stubbornly remains the case that the best students from China come here, not the other way around. Here are the main advantages the US currently enjoys:

    (1) Lag time. Everything in academia changes more slowly than elsewhere. Corporations come and go; Harvard’s been around for ~400 years (and across the pond, Oxford and Cambridge for ~1000).

    (2) The US has a culture of accepting huge numbers of immigrants from all over the world; most countries (including China) don’t.

    (3) All that, y’know, free speech stuff.

    One place where we can look for clues is history. It took, essentially, a World War and a Holocaust for the center of scientific gravity to shift from Europe to the US. Based on that one data point, we can speculate that a shift in scientific gravity away from the US, when and if it ever happens, might be a byproduct of some similarly cataclysmic event (e.g., a total collapse of the US economy, while some other part of the world—New Zealand?—remains fine).

  33. Scott Says:
    Comment #33 August 14th, 2011 at 3:24 am

    madhatter #29:

    Is there any reason to rule out a natural proof (in the sense of Razborov-Rudich) of an n^1000 lower bound for a problem?

    Actually, yes. Such a proof would let us break pseudorandom functions in ~2n^0.001 time.

  34. James Says:
    Comment #34 August 14th, 2011 at 3:34 am

    > Someone asked that in a previous Ask Me Anything. AI, applied computer security, and computational biology are all areas that I cheerlead from the sidelines.

    What’re you particularly interested in with regards to applied computer security?

  35. kiliva Says:
    Comment #35 August 14th, 2011 at 3:37 am

    1. Do you believe Israel will exist in 30-40 years as it exists now? Do you think balance of power will shift away from US and it will not be able to provide protection to Israel against the Arab world? Would Israel would have to be tame, and even submit to the War crimes tribunal, set up by the Arabs?
    2. What do you think of the plight of the Libyan people? Thousands of innocent victims, civil war and return of the most prosperous African country, that had free education, health service, cheep housing and high human development index into the stone age due to meddling of France and Britain (we now know that initial protest in Libya has been “helped” escalate by French secret service). Is it good to find US less hawkish about the issue than French and British (who have much more interest in Libyan oil)?
    3. Do you think that it is a good idea to have theocracy in Egypt, Libya etc.? Iran revolution led to theocracy, first liberals and religious fanatics worked together to topple western puppet dictatorship, and then liberals lost to fanatics.

  36. Carl Lumma Says:
    Comment #36 August 14th, 2011 at 3:39 am

    Vitanyi et al claim that for most algorithms, average-case running time approaches worst-case running time when an input’s likelihood of appearing is inversely proportional to its Kolmogorov complexity. They explain by saying, “Suppose algorithm A runs fast on some inputs and slowly on others. Then the particular input which causes A to run slowest has a short description, namely, “that input of size n which causes algorithm A to run slowest”. This is a description of length log n (plus some constant) which describes a string of length n. So the length-n string described has low complexity and is assigned a high probability… This is intuitively the reason why … such simple strings slow the average running time of A to its worstcase running time.”

    Why doesn’t this argument also apply to best-case inputs? Isn’t “the input of size n which causes algorithm A to run fastest” a simple description?

  37. abc Says:
    Comment #37 August 14th, 2011 at 3:47 am

    What’s your worst teaching horror story?

  38. Scott Says:
    Comment #38 August 14th, 2011 at 3:48 am

    dan #31:

    1. Where do your good new ideas come from? (i.e., what is your creative process? )

    Uhh, I’ll have to think back to when my last good idea was … maybe in grad school? 🙂

    Seriously, often it’s talking to people. Often it’s hearing something that annoys me because it seems obviously wrong, then thinking about why it’s wrong.

    Unlike other, more courageous people, I almost never work on something unless I already have a good idea of how to solve it. Even in those cases, the idea is usually wrong, so that I end up spending months where at first I thought an afternoon would suffice. And (like most researchers) I almost always end up solving a problem at least somewhat different from the one I thought I was going to solve—sometimes completely different. So then I have to “draw a target around where the arrow landed,” and pretend the problem that I managed to solve was the one I cared about all along.

    2. What is your process for deciding on which ideas to allocate time to?

    I have no process—I end up having spent time on something because it annoyed me. Do you have a process? If so, let me know what it is! 🙂

    3. Would you ever (realistically) leave academia? If yes, what would it take? If no, why not?

    Every time I visit the Googleplex, I think, “wow, this place is unbelievable! in a different life, I would’ve loved working here!” But in this life, academia—while I wouldn’t recommend it for everyone—turns out to suit my temperament extremely well. And crucially, there are a lot of strange and crazy directions that I could go off on, completely different from anything I’m doing now, without even leaving academia. So for me to leave, I guess it would really have to be a world-changing opportunity. And even then, maybe I’d just take a 2-year leave of absence. 🙂

  39. Jeffrey Says:
    Comment #39 August 14th, 2011 at 4:00 am

    What’s your favorite ice cream flavor?

  40. Dis Says:
    Comment #40 August 14th, 2011 at 4:00 am

    Who is your favorite science fiction writer?

  41. Sniffnoy Says:
    Comment #41 August 14th, 2011 at 4:01 am

    So what’s the status of the $25.00 challenge, and does whatever’s known about it generalize beyond straight-up decision problems?

    On the other hand, if you question whether arithmetical statements have objective truth-values, then I think you’re caught in an infinite regress! At that point you might as well reject modus ponens and 1+1=2.

    This gets me wondering… questions about proofs are questions about strings, which of course we can encode as whole numbers, so normally we don’t distinguish. But now I’m wondering if anyone has ever tried to directly axiomatize the workings of strings (binary ones? or what?) that would be the equivalent of PA for whole numbers? Wait, what sorts of things would it even talk about? I have no idea. (This is not a Scott-question, just general possibly-nonsensical musing.)

  42. Scott Says:
    Comment #42 August 14th, 2011 at 4:01 am

    James #34:

    What’re you particularly interested in with regards to applied computer security?

    Y’know, the stuff you read about in the news: the security of voting machines, copy-protection, worms and how to fight them, how to facilitate secure communication among dissidents in China and Iran. (I could have said, more-or-less equivalently: the stuff my friend Alex Halderman does.)

  43. wykipedyam Says:
    Comment #43 August 14th, 2011 at 4:02 am

    1. Do you edit wikipedia – if so, which articles and under which pseudonyms?
    2. Have you ever vandalised wikipedia (perhaps as a student)?
    3. Do you identify yourself more as a nerd or as a Jew?

  44. Daniel Says:
    Comment #44 August 14th, 2011 at 4:17 am

    How did your advisor Umesh Vazirani manage students? Many of his students, like you, Sudan, Arora and Ambainis, all become very successful scholars. Unbelievable.

  45. A Nonny Miss Says:
    Comment #45 August 14th, 2011 at 4:19 am

    How do you feel about free jazz?

  46. dan Says:
    Comment #46 August 14th, 2011 at 4:27 am

    > Do you have a process? If so, let me know what it is!

    I’m working on trying to figure it out–that’s why I asked! But my thought is that maybe a good starting point is the multi-armed bandit problem, where each idea (arm) is a slot machine with some unknown distribution of rewards. As you work on ideas (pull arms), you get to measure samples of the reward. Under this model, there are then various algorithms for deciding how to trade off exploration and exploitation.

    On the flip side, though, I ask this question to a lot of people who I consider very creative, and your answer is by far the most common. A very good songwriter I asked recently just looked at me funny and said roughly (but much more eloquently), “There are certain ideas that appear my head. When they come, I have no choice but to work on them. Otherwise, they’ll eat me, from the inside out.”

    So maybe the best process is to just let your subconscious take the steering wheel.

  47. Scott Says:
    Comment #47 August 14th, 2011 at 4:31 am

    kiliva #35:

    1. Do you believe Israel will exist in 30-40 years as it exists now?

    I wish that I could confidently say yes. (Although “as it exists now” is vague: if Israel ever achieves a peace deal, gets rid of the loonier settlements, reforms the coalition system that gives absurd power to small parties, ends the religious control over marriage, institutes a serious antismoking campaign, builds a subway in Tel Aviv, or does something about traffic congestion on the Ayalon freeway, those will be good changes.)

    Would Israel would have to be tame, and even submit to the War crimes tribunal, set up by the Arabs?

    I can’t imagine Israel ever submitting to an “Arab war crimes tribunal.” Furthermore, if the groups who would want such a tribunal ever obtained the power to hold one, it seems overwhelmingly likely to me that they’d skip the tribunal and proceed immediately to the “sentencing.”

    To put it differently, if Israel did go down, it’s hard to imagine how it would happen without a very destructive fight. We’re talking about a country that was founded on the principle of “never again,” and that has several hundred nuclear warheads.

    2. What do you think of the plight of the Libyan people? Thousands of innocent victims, civil war and return of the most prosperous African country, that had free education, health service, cheep housing and high human development index into the stone age due to meddling of France and Britain (we now know that initial protest in Libya has been “helped” escalate by French secret service). Is it good to find US less hawkish about the issue than French and British (who have much more interest in Libyan oil)?

    I think the plight of the Libyan people is terrible, but I don’t agree that the issue is “French and British meddling.” From what little I know, I’d say the main issue is that Qaddafi is a murderous dictator (though the opposition groups aren’t Care Bears either).

    3. Do you think that it is a good idea to have theocracy in Egypt, Libya etc.?

    No, I think it’s a terrible idea.

  48. Alexander Kruel Says:
    Comment #48 August 14th, 2011 at 4:32 am

    Can you think of any milestone such that if it were ever reached you would expect human-level machine intelligence to be developed within five years thereafter?

  49. Scott Says:
    Comment #49 August 14th, 2011 at 4:38 am

    Carl Lumma #36:

    Why doesn’t this argument also apply to best-case inputs?

    It does!

    Isn’t “the input of size n which causes algorithm A to run fastest” a simple description?

    It is!

    You answered your own questions.

    Unfortunately, the fact that the lowest possible running time is 0 means that the best-case inputs can’t drag down the average running time as much as the worst-case inputs drag it up.

  50. James Says:
    Comment #50 August 14th, 2011 at 4:41 am

    My question is about the usefulness of oracles in theoretical computer science. I can imagine one use which is nothing more than as a tool for divide and conquer– if you don’t know how to solve something but think someone might figure it out later, then you decree that you have an oracle for it and go on about your business.

    But this seems to me of pretty meager utility. So I suspect that there useful in some deeper way. The thing is, I can’t imagine what it is, assuming we’re ultimately only interested in real-life computable functions.

    Q: Are oracles more useful than just as linguistic device for divide and conquer, and if so how?

  51. Scott Says:
    Comment #51 August 14th, 2011 at 4:46 am

    What’s your worst teaching horror story?

    Just this spring, I designed a final exam for 6.045 (my computability and complexity class) that was absurdly too hard—the average was somewhere around 45%. Fortunately, the students calmed down once I reassured them that everything was curved and that, considering (in retrospect) the exam, they actually did quite well.

  52. Scott Says:
    Comment #52 August 14th, 2011 at 4:48 am

    Jeffrey #39:

    What’s your favorite ice cream flavor?

    I have to pick one? 🙂 I’m partial to mint chocolate chip, Ben & Jerry’s “Half-Baked,” and hot-fudge sundaes (often with coconut or burnt caramel ice cream) at Toscanini’s in Central Square.

  53. Scott Says:
    Comment #53 August 14th, 2011 at 4:51 am

    Dis #40:

    Who is your favorite science fiction writer?

    For the sake of my childhood self, I’ll have to go with Asimov. Lately, though, I’ve been a fan of Greg Egan, both because he writes about issues I care about deeply and because he occasionally comments on this blog.

  54. Scott Says:
    Comment #54 August 14th, 2011 at 4:52 am

    Everyone: Going to sleep now! Will continue answering questions in the “morning” (i.e., afternoon).

  55. Mohsen Says:
    Comment #55 August 14th, 2011 at 5:31 am

    It is not fair! wherer is my question? (BTW it is my second question. I know myslef!)

  56. Sniffnoy Says:
    Comment #56 August 14th, 2011 at 5:35 am

    Somewhat more of a heckle than a question, but #2. Are decision problems really *that* much easier to handle than more general problems? 🙂 And can’t you guys even bother to properly use the notation you invented for other problems? 😀 (Thinking here of the kerfuffle on Dick Lipton’s blog about whether or not factoring was actually poly-time on a quantum computer, due to confusion over what sort of subroutines are allowed.)

  57. Carl Says:
    Comment #57 August 14th, 2011 at 5:37 am

    OK, thanks for answering my question!

    The last question you should answer is, “What was your favorite question?” (Or something stupidly meta, like “Which questions will you not deign to mention?”)

  58. Alex Says:
    Comment #58 August 14th, 2011 at 5:54 am

    Do computational considerations affect the question of whether software patents are a good idea? Specifically, do you think the following argument holds:

    A property system requires not just ownership, but that it is possible to find out if a particular thing is owned, and who owns it. (Most obviuolsy, to try and avoid infringing. For a detailed argument, see Bessen and Meurer, http://www.researchoninnovation.org/dopatentswork/dopat3.pdf. De Soto’s “The mystery of Capital” also makes this point strongly.)

    Ideally, the lookup operation which answers this question should be implementable completely by a computer. For various reasons some human effort may be required, but it is essential limit this to O(1), or at most O(log(n)) in the size of the database.

    For land, clearly this operation is a lookup based on the location of the land. For something like a medical patent, its chemical name makes a natural search term with which one can eliminate (probably) all but O(1) patents from consideration.

    It seems to me that any lookup algorithm for software is going to fall foul of the halting problem. I’m not sure how to make that rigorous, but equivalence checking, which seems to be a similar problem, is known to be equivalent to the halting problem.

    On the other hand, there might be some get out clause whereby a lookup algorithm could be devised that works for ‘nearly all’ cases. What do you think?

  59. blk Says:
    Comment #59 August 14th, 2011 at 7:36 am

    What were the most significant developments/breakthroughs/insights in Quantum Computing (QC) of the last decade for you?

    What were the most significant developments/breakthroughs/insights in Complexity Theory (CT) of the last decade for you?

    Are there any areas of QC/CT that you think would be fruitful for more people to focus on, e.g. where probably a lot of progress could be made if only more people would get interested in this subarea?

  60. Joshua Zelinsky Says:
    Comment #60 August 14th, 2011 at 7:51 am

    Of the four requirements, it seems that #1 is getting ignored so I’ll ignore it also and put all three questions in a single comment:

    1. Many computer scientists believe that P=BPP. How likely do you think it is that there’s a maximum amount of speedup that can come from using a BPP algorithm, e.g. maybe algorithms in BPP never give more than an n^2 or n^3 speedup over the non-randomized version, or it is conceivable that there exist arbitrarily large k such that a deterministic algorithm can perform in n^a but BPP version can work in n^(a-k). Or is this just too removed from our current knowledge level to even speculate?

    2. For Godel’s incompleteness theorems to apply it is sufficient for an axiomatic system to contain Robinson arithmetic. Is there some equivalent statement known of the form “If a fragment F of Peano Arithmetic contains axiomatic system K, then being able to answer in polynomial time whether or not there is a proof of bounded length of a given statement in F implies P=NP”? (The phrasing here may be not completely good but I think the idea should be clear.)

    3. An alien comes up to you and tells you the following: You can give the alien one statement expressible in the language of ZFC. The statement must be a known mathematical conjecture (e.g. P=NP would be ok. But “P=NP has a proof of length less than Ackerman(100) in ZFC would be not ok since that’s not a conjecture.) If the statement has a proof or disproof the alien will provide it. If the supply is undecidable the alien will shoot you with its raygun. If you don’t supply a conjecture it will also shoot you with its raygun. What conjecture do you ask about?

  61. Manfred Steiner Says:
    Comment #61 August 14th, 2011 at 8:16 am

    Hey Scott, been waiting for this day all summer, all year. Got a case of beer, cigarettes, Miles Davis records, and a jar of olives. I will not move from the computer till the day is done. Had to call in sick but it’s worth the dressing down I’ll get tomorrow. There’s so many things I want to ask…but I don’t know how to begin. You ever been in this kind of a position?

  62. Dathan Says:
    Comment #62 August 14th, 2011 at 8:20 am

    Do you read Terry Tao’s blog with any regularity? Of the posts you do read, how many do you understand? Have you ever met Terry and if so what do you think of the man? People say he is the second smartest man on the planet (the first, obviously, is Donald Knuth).

  63. Vlad Says:
    Comment #63 August 14th, 2011 at 8:24 am

    How do you justify attending academic conferences, especially those held in distant lands? They seem tremendously self indulgent and wasteful affairs; when people are starving etc. how can we justify shelling out so much cash? I won’t attend any conferences I can’t bicycle to for this reason…

  64. Eria West Says:
    Comment #64 August 14th, 2011 at 8:59 am

    Do you read much scientific work written in languages other than English ?

  65. Grant Says:
    Comment #65 August 14th, 2011 at 9:40 am

    What’s the simplest thing in computer science or mathematics that you still don’t feel you have a good understanding of, even though it’s “well understood” — i.e. something that even though you’ve spent time looking at, it either took you a much longer time than normal to grok or you still feel like you haven’t grokked yet.

    For instance, an answer might be something like “Martingale random variables. I never understood them, and now I just avoid them like the plague and get around them in my research however I can.”

  66. Chris Says:
    Comment #66 August 14th, 2011 at 9:48 am

    Jivav
    ”In 1982 CH Bennett made a very interesting connexion between information and energy, noticing that “the essential irreversible step, which prevents [Maxwell’s] demon from breaking the second law, is not the making of a measurement […] but rather the logically irreversible act of erasing the record of one measurement to make room for the next”.

    1-Do you agree with this view?

    2- Can we infer from this view that the second law forbid the (physical) existence of oracle for data compression?

    3- Can we extend the idea to show that Closed Timelike Curves (P=PSPACE) or the collapse of the polynomial hierarchy (either P=NP or higher) would implicate free energy?”

    In 1982 CH Bennett made a very interesting connexion between information and energy, noticing that “the essential irreversible step, which prevents [Maxwell’s] demon from breaking the second law, is not the making of a measurement […] but rather the logically irreversible act of erasing the record of one measurement to make room for the next”.

    this may (or may not lol) be of interest:
    Entanglement and the Thermodynamic Arrow of Time by David jennings and Terry Rudolph
    http://arxiv.org/abs/1002.0314
    ”Extending work by Partovi, we consider a general entangled multipartite system that allows large reversals of the thermodynamic arrow of time. We describe a hierarchy of arrows that arises from the different correlations allowed in a quantum state and examine these features in the context of Maxwell’s Demon. We examine in detail the case of three qubits, and also propose some simple experimental demonstrations possible with small numbers of qubits”

  67. Chris Says:
    Comment #67 August 14th, 2011 at 9:57 am

    Do you think potential physically derived separations of complexity classes will lead to a deeper understanding of the nature of space and time? any intuitions about this??

  68. Scott Says:
    Comment #68 August 14th, 2011 at 10:38 am

    Mohsen #55:

    It is not fair! wherer is my question?

    Alright, fine. Since you asked, the way to become a professor at MIT is to start a blog and spend a lot of time answering random questions. Don’t get distracted by research!

  69. Calpurnia Says:
    Comment #69 August 14th, 2011 at 10:50 am

    Would you rather be the sole author of a proof that P ~= NP (or that P=NP) or be alive when an alien spaceship(s) visits earth for the first time?

  70. Scott Says:
    Comment #70 August 14th, 2011 at 10:58 am

    Sniffnoy #41:

    So what’s the status of the $25.00 challenge, and does whatever’s known about it generalize beyond straight-up decision problems?

    For those who don’t know or remember what “Sniffnoy” is asking about, see here.

    The status is that Broadbent, Fitzsimons, and Kashefi came very close to solving the problem in this breakthrough paper (see also the closely-related independent work by Aharonov, Ben-Or, and Eban).

    The catch is that the verifier in their protocol needs to be slightly quantum, enough to prepare single unentangled qubits and send them to the prover (but nothing more than that). Or you can also run their protocol with a completely classical verifier and two entangled BQP provers.

    I paid Broadbent, Fitzsimons, and Kashefi $15 to share amongst themselves, and later paid Aharonov, Ben-Or, and Eban another $15 to share amongst themselves.

    The “full” $25 challenge—i.e., whether a single BQP prover can prove everything in BQP to a completely classical verifier—remains open, in both the relativizied and unrelativized variants.

  71. Scott Says:
    Comment #71 August 14th, 2011 at 11:09 am

    wykipedyam #43:

    1. Do you edit wikipedia – if so, which articles and under which pseudonyms?

    Very occasionally, if I see an easily-fixable error or omission I’ll go in and fix it anonymously. But I don’t even remember which articles, and I’ve never created an actual account there.

    2. Have you ever vandalised wikipedia (perhaps as a student)?

    Once, in an extremely minor fashion (for an inside joke among friends). It was quickly reverted.

    3. Do you identify yourself more as a nerd or as a Jew?

    I’ll have to go with nerd. For I can easily imagine having been a nerdy WASP, nerdy Indian, etc. (and still being recognizably “me”), but I can’t easily imagine having been a sports-loving, hard-partying, Jersey Shore-watching Jew.

  72. Scott Says:
    Comment #72 August 14th, 2011 at 11:18 am

    Daniel #44:

    How did your advisor Umesh Vazirani manage students?

    LOL—mostly, he didn’t! 😀 Students were simply drawn to him by his indescribable charisma and charm—and then, once in his inner circle, they learned by seeking to emulate him, and by parsing his enigmatic wisdom.

    Umesh was a great advisor.

  73. Scott Says:
    Comment #73 August 14th, 2011 at 11:24 am

    A Nonny Miss #45:

    How do you feel about free jazz?

    All for it! My brother David is actually the drummer for a Stevie Wonder cover band in NYC called The Shades (you can watch them here—they’re good!), and a few months ago I had the pleasure of attending one of their (free) shows, at a club called the Stone Rose.

    UPDATE: David has informed me that “free jazz” is a style of jazz, not jazz that you don’t pay for. This illustrates a general point: that while I enjoy music, I use him as an oracle for essentially all musical knowledge.

  74. Scott Says:
    Comment #74 August 14th, 2011 at 11:32 am

    Alexander Kruel #48:

    Can you think of any milestone such that if it were ever reached you would expect human-level machine intelligence to be developed within five years thereafter?

    Uhh, Neanderthal-level machine intelligence?

    Interrogator: So, tell me what you’re thinking about today.
    AI: OOGA BOOGA. AI HUNGRY. AI HUNT VIRTUAL MAMMOTH.

  75. Lukasz Grabowski Says:
    Comment #75 August 14th, 2011 at 11:36 am

    1) If you were asked to draw on the map the borders for the pallestinian state, and you were guaranteed that they will be respected, how would you draw them?

    2) I was once told that the class logspace is equal to the class of languages recognizable by read-only Turing machines with multiple readers. Do you know a reference for that?

    3) What are currently the open problems concerning logspace?

  76. personalsaga Says:
    Comment #76 August 14th, 2011 at 11:37 am

    Recent polls have shown a fifth of Americans can’t locate the US on a world map. Why do you think this is?

  77. Number Freak Says:
    Comment #77 August 14th, 2011 at 11:39 am

    What are your greatest fears?

  78. Raghu Says:
    Comment #78 August 14th, 2011 at 11:52 am

    As a grad student, I was deeply impressed by your take down of scientific publishing racket and took to publishing in open-access (biology) journals. Can you share your thoughts on the current scenario with some in-roads made by open-access journals, preprint outlets, stackoverflow-type peer-review, etc.? Also, arXiv at 20. Thanks!

  79. Alexander Kruel Says:
    Comment #79 August 14th, 2011 at 11:54 am

    What probability do you assign to the possibility of human extinction as a result of badly done artificial general intelligence? P(human extinction | badly done AGI) = ?

  80. Shamu Says:
    Comment #80 August 14th, 2011 at 12:05 pm

    Do you believe there is a God who intervenes in our world? If so, can you characterize the intervention?

  81. mit2013 Says:
    Comment #81 August 14th, 2011 at 12:20 pm

    Which single generalization about us undergraduate MIT students can you make with greatest accuracy?

  82. kiliva Says:
    Comment #82 August 14th, 2011 at 12:30 pm

    Thanks for the answers. It is a bit disappointing to read that you have difficulty imagining Arab war crimes tribunal:

    ” Furthermore, if the groups who would want such a tribunal ever obtained the power to hold one, it seems overwhelmingly likely to me that they’d skip the tribunal and proceed immediately to the “sentencing.” ”

    This is a bit strange, coming from someone who also has difficulty understanding what is wrong with vigilante justice (in the case of Osama bin Laden, against views of Chomsky,. seeing no problem with bullet with no trial).

    Also, it is perhaps worth pointing out that there are many people, not only in Arab world but in Europe and other parts of the world that think war crimes happened in Israel-Palestinian conflict.

    Perhaps you imagine that most Arabs are not capable of understanding the importance of the tribunal (and are not civilized enough to proceed in this manner, but prefer “swift justice” of lynching).

    War crimes tribunals serve important role, that goes beyond mere justice. Cynics would say that they have propaganda value of establishing truth for history, or rather a version of victor truth and history written by the winners. Even show trials have this important aspect. Stalin regime could have easily executed those it wished (and indeed it did such things), but show trials were important for propaganda reasons. Nuremberg trials were also important, especially for establishing record for posteriority and also for convincing Germans of their guilt (that was not accepted in population more widely until 70s in Germany). Tribunals also played important role in South Africa for moving beyond apartheid for both whites and blacks etc.

    To think that Arabs do not understand this role and importance of tribunals, despite of the fact that even some people in US do not fully grasp its role, comes off, frankly, as a bit racist. Arabs in fact do understand well role of propaganda in the Israel-Palestinian conflict, and they demonstrate it daily on Al-Jazeera and other places. This propaganda is sometimes especially gauged for Europeans and it has been quite effective (not going into question how much it is based on truth or justified – which is question for any propaganda effort).

    So, there are many activists in Arab world that would rather see a tribunal like Nuremberg than just execute their perceived oppressors. Tribunals are not so much instruments of revenge or retribution, as they serve a purpose for enshrining new historical truths, weather based on real truth or not, a goal that can only be obtained with “soft” methods, as this effort is directed to the outside world (Europe, China, Latin America, even US) where tribunal organizers would not have direct control.

  83. Scott Says:
    Comment #83 August 14th, 2011 at 12:31 pm

    James #50:

    Q: Are oracles more useful than just as linguistic device for divide and conquer, and if so how?

    YES! Oracles show up all over the place, sort of like complex numbers (another concept whose numerous uses are hard to imagine when you first encounter them). Here are the first six examples that popped into my head:

    1. Reductions. If you want to show a problem is hard, you show that using an oracle for that problem, you could solve some problem we already think is hard.

    2. Relativization. If you want to show that special techniques would be needed to collapse two complexity classes, you construct an oracle that separates them.

    3. Often, “oracle” is simply interchangeable with “very long input string.”

    4. In computational learning theory, “oracle” is often interchangeable with “teacher” or “the external environment.”

    5. Most of the quantum algorithms we have (including Simon’s and Shor’s algorithms) are best explained in the oracle model.

    6. If you want to show something is unlikely, you show that its truth would collapse two oracle-defined complexity classes. A classic example is the Karp-Lipton Theorem: if NP has polynomial-size circuits, then NPNP = coNPNP. A more recent example is my paper with Arkhipov, where we show that if a certain optical experiment can be efficiently simulated classically, then P#P = BPPNP.

  84. Ungrateful_Person Says:
    Comment #84 August 14th, 2011 at 12:40 pm

    One question (if I may).

    To be direct, I know my question is vague (possibly even stupid, given my current understanding of Computational Complexity). First, allow me to ramble a little. Really, the post is asking one (main) question but since I am not sure if I can express myself, you will see several question marks.

    I recently started learning Computational Complexity. The field is fascinating but often I feel that there should be a something like “A history of complexity theory” which puts some ideas in context so that they do not seem coming out of thin air (at least to me). A simpler question first. Am I the only one who feels this way? I mean is Computational Complexity a field that deserves a text detailing it through its history given that it has been actively explored only for 4 decades.

    Now my question (as I said before, its a little vague). While studying interactive proofs and a little about the PSPACE class, I was not really sure what was going on. What I mean here is that how does one get the insight (or what makes one care enough to explore the possibility) that allowing interaction and randomness in a proof allows one to go beyond the traditional notion of proof. Was it something like a “random exploration” which paid off (this better not be true, and I think it is not)?

    Again, the question basically is what led people to do research in this area? What is (if any) the missing piece in this historical framework? Why should even a theory person bother studying about interaction?

    And finally, if you will allow me one more (no problems if you do not) can you say in retrospect (giving an intuitive justification) why was it the case that IP = PSPACE?

  85. Scott Says:
    Comment #85 August 14th, 2011 at 12:42 pm

    Sniffnoy #56:

    Are decision problems really *that* much easier to handle than more general problems? 🙂 … Thinking here of the kerfuffle on Dick Lipton’s blog about whether or not factoring was actually poly-time on a quantum computer, due to confusion over what sort of subroutines are allowed.

    No, decision problems aren’t that much easier to handle, and indeed these days people talk about other types of problems (e.g., sampling and search problems) plenty often. On the other hand, when you’re comparing different complexity classes, it helps to have a uniform standard.

    Regarding Lipton, I have to tell you that “Is Factoring Really In BQP? Really?” was my least favorite post in the history of his blog. Yes, factoring is in BQP no matter how you formalize the statement; that really was just an avoidable confusion over nothing.

  86. Ungrateful_Person Says:
    Comment #86 August 14th, 2011 at 12:49 pm

    Now an even dumber question(I blame my non-mathematical background. Note that the following is in context of zero knowledge proofs)

    Why do we say at all interaction helps with a proof when what really happens is that the Prover proves something and tries to convince the verifier that he really knows the proof.

    I will try making what I mean more clear. Its only the Prover who knows the proof (or is falsely claiming he knows it; but lets disregard that case for now). The Verifier is not involved at all in the proof constructing process of the Prover. All he does is to check the Prover’s claim that he knows the proof without having taking any part in the proof construction process himself.

    So, all this process allows is just Verification (which is what you expect the Verifier to do).

    What I really want to know is that can interaction help us come up with a proof of RH or some other hitherto unproved mathematical theorem. Or all it really does is to verify whether a proof in possession of a super natural being is correct?

  87. Jiav Says:
    Comment #87 August 14th, 2011 at 12:50 pm

    Scott #3,

    Thanks for your insights.

    2′- yes, a physical object which would, given a string x, returns the smallest Turing machine that outputs x. For why it should violate second law, I’d go as follow:

    (a) From CH Bennett 82, free blank state equals free energy.

    (b) From WH Zurek 89,

    “The key result relevant to the discussion of the thermodynamic costs of information processing can be stated as follows. Suppose string r2 can be computed from the program r1 by a Turing machine T. If we demand that the computation should start with only r1 on the tape (which assumes that r1 is self-delimiting) and end with nothing but r2, then the Turing machine must erase no less than K(r1)—K(r2) bits in the process.”

    (c) physical randomness produces independant events, thus random strings have (typically high but) submaximal Kolmogorov complexity

    b+c => (d) most physically-produced random string r1 can be turned to describe a new-coming string r2 at a cost of K(r1)-K(r2) blank states however finding the correct path for (d) requieres hypercomputation.

    a+d+e => hypercomputation would provide free energy

    On second thought however, this demo makes two extra assumptions in addition to hypercomputation: that physical randomness does not produce strings having maximal Kolmogorov complexity; and that hypercomputation would be thermodynamically free or below some threshold. I don’t know if there is a better proof or if it’s possible to relax these assumptions.

    3′- was it a personal communication or Seth Lloyd produced a paper somewhere?

    Chris #66

    Thanks, but I must say I couldn’t follow the argument. Could you popularise it?

  88. Ungrateful_Person Says:
    Comment #88 August 14th, 2011 at 12:50 pm

    And one last (you allow 3 per person).

    What is your favorite movie, your favorite novel and your favorite piece of mathematical work?

  89. Scott Says:
    Comment #89 August 14th, 2011 at 1:52 pm

    Dathan #62:

    Do you read Terry Tao’s blog with any regularity?

    Sure.

    Of the posts you do read, how many do you understand?

    Eh, sometimes I follow him, sometimes I don’t, most often I convince myself that I could follow if I invested enough time—after all, he’s made the matter almost as clear as it can be made—but then other work intervenes. In other words, probably the same relationship that some people have to (the technical parts of) this blog. 🙂

    Have you ever met Terry and if so what do you think of the man?

    I’ve corresponded with him, but I’ve only met him once (very briefly) at a conference. Obviously I’m in awe of him just like everyone else.

    Someone once told me that the one thing they can’t stand about Terry is how normal and nice he is: isn’t it the least we can ask that anyone at his level be a crazy recluse with five-inch fingernails?

  90. Scott Says:
    Comment #90 August 14th, 2011 at 12:54 pm

    Alex #58:

    Do computational considerations affect the question of whether software patents are a good idea?

    Interesting question! However, I think the “complexity” issue you raise applies much more generally than just to software: it applies to any patents on abstract intellectual ideas with ill-defined boundaries, in medicine, engineering, etc. That’s why patent law is such a large and lucrative field!

    For whatever it’s worth, I think that way too many patents are granted today, for ideas that are way too obvious. The phenomenon of patent trolls is an obvious indicator of this. I don’t think there’s any “absolute right” to patents—the purpose of the patent system is solely to encourage innovations—but right now it’s on balance doing the opposite. Of course, I’m far from alone in thinking the patent system needs serious reform—but partly because of the immense lobbying power of e.g., the pharmaceutical companies, if anything the system seems to be getting even more irrational.

  91. Alexander Kruel Says:
    Comment #91 August 14th, 2011 at 12:56 pm

    What would you do with $1,000,000 if it were given to you on the condition that you donate it to a charity of your choice?

  92. Steve Flammia Says:
    Comment #92 August 14th, 2011 at 1:00 pm

    What were your three favorite quantum information theory results in the last year? To jog your memory, you can find the top scited papers from the last 365 days here: http://www.scirate.com/index.php?multi=365 . Please also give a brief explanation why you liked the paper.

  93. semafors4 Says:
    Comment #93 August 14th, 2011 at 1:05 pm

    On a political compass where do you stand:

    1. On economic scale, are you more left or right
    2. On social scale, are you more authoritarian or libertarian
    3. If you have any test scores related to this, what are they?

  94. Scott Says:
    Comment #94 August 14th, 2011 at 1:10 pm

    blk #59:

    What were the most significant developments/breakthroughs/insights in Quantum Computing (QC) of the last decade for you?

    Here’s an adaptation of a list that I recently sent to Michael Nielsen (though a few of them fall just past the 1-decade mark):

    Quantum walk algorithms (especially for element distinctness and game tree search)

    The adiabatic algorithm and analysis of it

    Progress on quantum lower bounds (collision & element distinctness, the “modern” adversary method and Reichardt’s proof of its optimality)

    Progress on quantum communication complexity (Disjointness lower bound, Hidden Matching problem)

    Cluster-state and one-way QC

    Blind/authenticated quantum computing

    QIP=PSPACE

    Valiant’s noninteracting-fermion model, and the discovery of many other nonuniversal QC models (noninteracting bosons, commuting Hamiltonians…)

    Matrix product states and area laws

    TQFT = Jones polynomial = BQP

    What were the most significant developments/breakthroughs/insights in Complexity Theory (CT) of the last decade for you?

    PRIMES is in P

    L=SL

    NASH is PPAD-complete

    Many developments in PCP, including Irit Dinur’s combinatorial proof

    Fully homomorphic encryption

    NEXP⊄ACC

    I’m sure there are others I’m forgetting…

    Are there any areas of QC/CT that you think would be fruitful for more people to focus on, e.g. where probably a lot of progress could be made if only more people would get interested in this subarea?

    In some sense, the papers I write are the “putting my money where my mouth is” answer to that question! But, OK…

    Complexity theory of sampling problems

    Complexity of “naturally-occurring” physical systems (e.g., quantum systems that might yield intermediate complexity classes between BPP and BQP)

    Complexity issues in Darwinian evolution (not necessarily limited to Valiant’s evolvability model)

    Complexity issues in neuroscience

    Obfuscation of code and proofs (including more limited types of obfuscation than the usual type)

  95. serialmoth Says:
    Comment #95 August 14th, 2011 at 1:11 pm

    1. What do you think about Richard Lipton and company again rising Deolalikar from the dead on their blog?
    2. Did you read last year’s shredding into pieces of this paper and what do you think about it?
    3. Do you think the whole infamous episode was positive (due to publicity) or negative for the TCS community?

  96. Scott Says:
    Comment #96 August 14th, 2011 at 1:31 pm

    Joshua Zelinsky #60:

    Of the four requirements, it seems that #1 is getting ignored so I’ll ignore it also and put all three questions in a single comment:

    Yeah, everyone ignored my “no lists of questions rule” from the very beginning! Oh well…

    1. …How likely do you think it is that there’s a maximum amount of speedup that can come from using a BPP algorithm, e.g. maybe algorithms in BPP never give more than an n^2 or n^3 speedup over the non-randomized version…

    This is actually a fantastic research topic—one that Dana and I talked about some time ago but never really worked on. Can we find some assumption that would imply “super-duper-strong” derandomization (much tighter even that P=BPP)? Alternatively, can we give evidence against super-duper-strong derandomization?

    If you’re willing to consider sublinear complexities, then we know that there exists an n vs. n0.753 separation for a total function (game-tree evaluation), and even an n vs. O(1) separation for a promise problem (e.g., whether the input string contains >2n/3 or <n/3 ones). So let’s assume that we’re talking about superlinear complexities only.

    In that case, I consider it within the realm of possibility that any problem solvable in T steps by a BPP machine is solvable in Tn steps, or conceivably even fewer steps, by a P machine. (UPDATE: Tn would seem like a natural bound, since there are 2n inputs of size n, and we’d at least want to amplify a randomized algorithm until it succeeds on all of them w.h.p. On the other hand, I know of no compelling argument that one couldn’t do even better than that.) But even if it’s someday proved that P=BPP, the (first) proof would almost certainly involve horrendously larger blowups than that.

    2. … Is there some equivalent statement known of the form “If a fragment F of Peano Arithmetic contains axiomatic system K, then being able to answer in polynomial time whether or not there is a proof of bounded length of a given statement in F implies P=NP”?

    But of course! How about propositional logic with one existential quantifier? Or even just the fragment of propositional logic we know as 3SAT? 🙂

    3. An alien comes up to you and tells you the following: You can give the alien one statement expressible in the language of ZFC. The statement must be a known mathematical conjecture … If the statement has a proof or disproof the alien will provide it … What conjecture do you ask about?

    Will the alien give me a formal ZFC proof, or a humanly-understandable proof? (Actually, I’m not sure how that would affect my answer.)

    Maybe I’d ask whether there’s a 2O(√n) quantum algorithm for 3SAT.

  97. Scott Says:
    Comment #97 August 14th, 2011 at 1:35 pm

    Manfred Steiner #61:

    Hey Scott, been waiting for this day all summer, all year. Got a case of beer, cigarettes, Miles Davis records, and a jar of olives. I will not move from the computer till the day is done. Had to call in sick but it’s worth the dressing down I’ll get tomorrow. There’s so many things I want to ask…but I don’t know how to begin. You ever been in this kind of a position?

    LOL! Not really, except (I guess) on the other side of it.

    Also: you work on Sundays? Where do you live?

  98. Scott Says:
    Comment #98 August 14th, 2011 at 2:13 pm

    Vlad #63:

    How do you justify attending academic conferences, especially those held in distant lands? They seem tremendously self indulgent and wasteful affairs; when people are starving etc. how can we justify shelling out so much cash?

    You can ask the same question about almost any expensive human activity; why focus on academic conferences specifically? (E.g., “How can anyone justify having children when the world is so overpopulated as it is?”)

    I guess we all need to give our own answers to these questions, but here are mine:

    1. Scientific research is a tiny layer of froth on the vast cauldron of human wastefulness, but it’s disproportionately important froth. Why should STOC and FOCS be canceled, while the marketing and textile-manufacturer conventions that make up 99% of the business at the same hotels continue unabated?

    2. In my experience, conferences do have scientific value: while most of the talks are indeed wastes of time, conferences are the way I met my colleagues and became part of the field as a grad student, and I count eight of my papers that had their origin at one conference or another.

    3. Having said that, I agree that we currently have way too many conferences in quantum computing and TCS: it’s ridiculous to fly halfway around the world to talk to the same people you talked to last week at a different conference. I’ve been struggling for years (not always successfully) to cut back on travel. Having to teach every semester definitely helps.

  99. Len Ornstein Says:
    Comment #99 August 14th, 2011 at 2:17 pm

    Do you think it’s important that the public and policy makers understand the difference:

    between typical, deductive, axiomatically-derived, ‘eternal’ ‘absolute truths’ of logic and math (as well as of the more sloppy, dogmatic, ‘axiomatically-derived’ truths of many other disciplines); and

    the inescapable – often-sloppy but improvable – residual uncertainties of the ‘facts’ produced by the , inductive approach to provisional, empirical ‘truth’ (including that of all scientific ‘knowledge’) ?

    If you agree that it’s important – and largely ignored, even in the education of most scientists and mathematicians – (briefly) ‘how’ should ‘we’ try to fill this educational gap?

  100. the reader from Istanbul Says:
    Comment #100 August 14th, 2011 at 3:20 pm

    1- Computers with CTCs which are just 1-bit wide have recently been shown to be equivalent to computers with postselection, and so PP=PostBQP=BQP_{CTC1}. Since BQP_{CTC}, i.e, the class of languages recognized by polynomial time quantum computers with polynomially wide CTCs, equals PSPACE, if PP doesn’t equal PSPACE, there must be an intermediate width of the CTC beyond which the time-traveling bits start adding more power to the machine. What’s your guess about this intermediate function, and why do you feel so?

    2- Is there a CTC model other than Deutsch’s which is simple enough that CS people can understand and nontrivial enough to be interesting that you think deserves to be given the same treatment that you gave to Deutsch’s?

  101. Scott Says:
    Comment #101 August 14th, 2011 at 3:41 pm

    Eria West #64:

    Do you read much scientific work written in languages other than English ?

    None.

    The only other language that I read even a little is Hebrew, but I wouldn’t know enough to read a Hebrew scientific paper, supposing such a thing existed (I’ve never seen one). Occasionally (every 4 years or so), I’ll come across a paper that I want to read in one of the “salad dressing languages” (French or Russian), but I can’t read either of those at all.

  102. Luca Says:
    Comment #102 August 14th, 2011 at 3:44 pm

    What’s your favourite CS-theory/math book and why do you love it?

  103. Anon Says:
    Comment #103 August 14th, 2011 at 3:45 pm

    Has the “Physics for Doofuses” column been discontinued because you’re no longer a doofus? Or are there merely too many other things competing for your meager supply of blog-posting resources?

    Keep up the good work, btw. We’re all happy that you’re here.

  104. Scott Says:
    Comment #104 August 14th, 2011 at 3:55 pm

    Grant #65:

    What’s the simplest thing in computer science or mathematics that you still don’t feel you have a good understanding of, even though it’s “well understood”…

    I don’t even know where to begin!

    – The switching lemma
    – The simplex algorithm
    – Continued fractions
    – Universality results for quantum gates
    – Anything related to representation theory
    – Design of gadgets for NP-completeness reductions
    – Auction theory
    – Pretty much anything that I was never forced to learn because I needed it for a class I was teaching or a paper I was writing!

  105. Scott Says:
    Comment #105 August 14th, 2011 at 3:58 pm

    Chris #67:

    Do you think potential physically derived separations of complexity classes will lead to a deeper understanding of the nature of space and time?

    Sorry, I have no idea what you mean by “physically derived separations of complexity classes.”

  106. Scott Says:
    Comment #106 August 14th, 2011 at 4:01 pm

    Calpurnia #69:

    Would you rather be the sole author of a proof that P ~= NP (or that P=NP) or be alive when an alien spaceship(s) visits earth for the first time?

    That depends pretty strongly on whether the aliens are friendly or hostile! 😀 Since you didn’t specify, I’ll have to go for the P≠NP proof.

  107. Scott Says:
    Comment #107 August 14th, 2011 at 4:14 pm

    Lukasz Grabowski #75:

    1) If you were asked to draw on the map the borders for the pallestinian state, and you were guaranteed that they will be respected, how would you draw them?

    More-or-less where the majority of Israelis would want it drawn. Israel would get everything behind the ’67 line, most of Jerusalem, and most of the settlements behind the current security fence; the Palestinians would get the rest.

    The Palestinians, of course, had many opportunities for a much better deal between 1947 and today and rejected all of them. On the other hand, if the peace process ever seriously starts again, Israel will probably again offer a better deal, and I think it will be justified in doing so.

    Incidentally, I don’t imagine for a picosecond that this conflict is really “about” the exact location of the borders. If it was, then it would’ve been solved 60 years ago!

    2) I was once told that the class logspace is equal to the class of languages recognizable by read-only Turing machines with multiple readers. Do you know a reference for that?

    Sorry, I don’t!

    3) What are currently the open problems concerning logspace?

    No doubt the two biggest ones are L versus RL and L versus NL.

  108. Vadim P Says:
    Comment #108 August 14th, 2011 at 4:17 pm

    Followup to a question from a previous Ask Me Anything: you mentioned that MIT Press was publishing a book based on you your Quantum Computing Since Democritus lectures. Is it still planned? Any ETA?

  109. the reader from Istanbul Says:
    Comment #109 August 14th, 2011 at 4:19 pm

    Lukasz Grabowski #75:

    About your question that goes
    ————-
    2) I was once told that the class logspace is equal to the class of languages recognizable by read-only Turing machines with multiple readers. Do you know a reference for that?
    ————-:
    The reference is:

    ACTA INFORMATICA
    Volume 1, Number 4, 336-344, DOI: 10.1007/BF00289513
    On non-determinancy in simple computing devices
    Juris Hartmanis

  110. Scott Says:
    Comment #110 August 14th, 2011 at 4:23 pm

    personalsaga #76:

    Recent polls have shown a fifth of Americans can’t locate the US on a world map. Why do you think this is?

    Because they’re busy pursuing more pleasurable activities than geography, like watching football and having sex. Also, because they’re very stupid.

  111. Scott Says:
    Comment #111 August 14th, 2011 at 4:30 pm

    Number Freak #77:

    What are your greatest fears?

    Environmental destruction, nuclear war, global economic collapse caused by soaring energy prices, dying in a car crash, and dogs (especially the smaller ones—I’ve found they’re actually more likely to bite)

  112. AmateurBlogReader Says:
    Comment #112 August 14th, 2011 at 4:33 pm

    Was my question early on too naive to warrant answer or maybe it was overlooked, or maybe there’s no short answer? I’m stating it again. If in attacking P vs NP, researchers fix their sight on a particular NP hard problem, e.g. generalized TSP and try to reason about the particular structure of the problem, are the oft quoted barriers to proofs of P vs NP the obstacle or is there something else? Does anyone know how to try and reason about something like this – fix a “natural” problem in P (e.g. TSP) of size n and try to prove a lower bound of n^k. Would such techniques if successful give insights for the general case? Are there “natural” NP-complete or NP-hard problems for which a “non-trivial” polynomial lower bound is known and how did they reach there?

  113. captiveted Says:
    Comment #113 August 14th, 2011 at 4:37 pm

    1. Are you a Zionist? To what extent you identify with Jewish nationalism?

    2. Are you a pacifist, or a militant? Do you support Iraq invasion? What is your opinion about Vietnam war?

    3. Are you for death penalty? Abortion?

  114. oligogal-c Says:
    Comment #114 August 14th, 2011 at 4:41 pm

    Have you ever experimented with (i.e. tried) drugs, and if you have, what drugs have you tried? What do you think about legalization of marijuana? What is your favorite alcoholic beverage (if any)?

  115. Scott Says:
    Comment #115 August 14th, 2011 at 4:44 pm

    Raghu #78:

    Can you share your thoughts on the current scenario with some in-roads made by open-access journals, preprint outlets, stackoverflow-type peer-review, etc.? Also, arXiv at 20.

    I’m convinced that the open-access side will win, although it might take a couple more decades. It’s a lot like gay marriage: the value of open-access is completely obvious to most of the younger generation (to whatever extent they think about it at all), but there’s a nontrivial time lag until the prominent researchers who are deeply entwined in the current Elsevier racket retire.

    As for the arXiv, happy 20th birthday! May it enjoy many more.

  116. LonePeep Says:
    Comment #116 August 14th, 2011 at 4:48 pm

    If you had to pick two or three papers to be verified using Isabelle/HOL/Coq or some other computer assisted theorem prover, which would they be and why?

    I’m interested in selections where the justification is more along the lines of: “…such and such a proof is extremely tedious, counterintuitive, or otherwise difficult for a human to understand…” as opposed to: “…such and such a proof is foundational and few alternate derivations exist…”.

  117. Scott Says:
    Comment #117 August 14th, 2011 at 4:50 pm

    Alexander Kruel #79:

    P(human extinction | badly done AGI) = ?

    How do you define “badly done”?? If it means “willing and able to cause human extinction,” then I’d say that the probability is close to 1. 🙂

  118. LonePeep Says:
    Comment #118 August 14th, 2011 at 4:54 pm

    Since there are three questions total per person: if you had to pick one or two mathematics classes (normally not considered to be under the umbrella of computer science) – topology or algebraic geometry for instance – that have surprisingly or unexpectedly come in handy during your research career, which would they be?

  119. Scott Says:
    Comment #119 August 14th, 2011 at 4:57 pm

    Shamu #80:

    Do you believe there is a God who intervenes in our world?

    I see no evidence for such a God. If there is one, where was He during the Holocaust, Stalin’s purges, Pol Pot’s genocide, etc.—playing World of Warcraft?

  120. Scott Says:
    Comment #120 August 14th, 2011 at 5:00 pm

    mit2013 #81:

    Which single generalization about us undergraduate MIT students can you make with greatest accuracy?

    You guys rock! GO BEAVERS!

  121. Luke Says:
    Comment #121 August 14th, 2011 at 5:10 pm

    Do you think there’s a chance computers will find a proof of PvNP before humans do? What sort of probability would you assign to that?

    The consequences of knowing for sure P!=NP might be smallish (most everyone proceeds with the assumption P!=NP), but what sort of impact would you guess knowing how to *prove* P!=NP would have?

  122. Scott Says:
    Comment #122 August 14th, 2011 at 5:11 pm

    kiliva #82, at the risk of instigating another flamewar, I can’t help but ask: do you also feel that there should be “war crimes tribunals” for the other side of this conflict? (You know, the side much of whose leadership has for 65 years both stated and pursued the goal of wiping Israel off the face of the earth?) Or would the tribunals be for Israel only?

  123. Amirali Says:
    Comment #123 August 14th, 2011 at 5:15 pm

    Scott #112:
    In case you didn’t realize:
    http://www.youtube.com/watch?v=lj3iNxZ8Dww
    —-

    Questions: What do you think of Obama? Predictions for 2012 elections?

  124. CrankyMcCrank Says:
    Comment #124 August 14th, 2011 at 5:26 pm

    Have you ever gave up some time to find a proof for P not equal NP? What was your strategy?

  125. Chris Says:
    Comment #125 August 14th, 2011 at 5:31 pm

    separation of complexity classes relative to some physical oracle as in the work of Beggs, Costa et al. was what i was talking of

  126. John Sidles Says:
    Comment #126 August 14th, 2011 at 6:10 pm

    I would like to (1) ask a question, (2) give a response to one of Scott’s requests, and (3) offer a concrete suggestion for student-level research. The question is simple:

    Scott, what are your three favorite yellow books?

    Please don’t interpret “yellow” too literally … any remarks at all relating to enjoyable reading, whether mathematical or otherwise, would be very welcome and interesting.

    The response is to Scott’s request (comment #16 above):

    “There are some results (I don’t remember a reference offhand— does anyone?) suggesting that simulating Newtonian physics could even be uncomputable!”

    A reasonable starting point is Donald Saari’s and Zhihong Xia’s thoroughly enjoyable survey “Off to infinity in finite time” (Notices AMS, 1995). The Saari-Zhang survey explains why Newtonian trajectories of point particles are uncomputable even when the particles never collide … readers of Shtetl Optimized might want to guess in advance how this uncomputability comes about!

    The Saari-Zhang survey does not associate computational extravagance to non-collision classical singularities (as they are called). Thus one possible student-level research program would be to design a concrete set of hypercomputation-capable Fredkin-Toffoli logic gates (also known as “billiard-ball gates”) based upon Saari-Zhang non-collision singularities. A thorough literature search would be prudent before beginning (my own just-now preliminary search found nothing).

    A suggested starting dynamical analysis, that in itself might be a good student project, and that is associated to a specific mathematical conjecture, derives from the discussion on Scott’s immediately preceding post Why Philosophers Should Care About Computational Complexity, specifically the discussion in comments #127, #131, and #131 of Aaron Fenyes’ preprint “Limitations on cloning in classical mechanics”(arXiv:1010.6103v2 [math-ph]).

    The motivation is that Fenyes’ analysis of classical and quantum cloning is asymmetric in that it compares quantum state-spaces that are compact (qudit product spaces) to classical state-spaces are open (Newtonian particles). The research objective is to confirm (or refute) Fenyes’ stated conjecture that cloning is possible for all classical systems. The research strategy is to analyze Fenyes-type classical cloning on a compact classical state-spaces. The suggested starting state-space is the canonical example of a compact classical state-space, namely S2, which is endowed with a natural symplectic structure ι* ∗ dr, where ι is the Cartesian immersion of S2 in R3, r is the radial coordinate function in R3, dr is the exterior derivative, ∗ is the Hodge dual operation, and ι* is the pullback onto S2.

    The preceding terminology sounds arcane … and yet the resulting classical dynamics is — “simply”, “obviously” or even “trivally” geometric dynamicists might say — the familiar Bloch dynamics that is found in every QM textbook. Heck, any other result would imply mathematically natural Hamiltonian flows on S2 that physicists didn’t know about! Moreover, all of the preceding geometric terms have mathematically natural definitions that can be conveniently explored on Wikipedia (or explored more traditionally by working backwards from, e.g., problems 14-12 and 14-13 of Jack Lee’s Introduction to Smooth Manifolds). These are good tools for students to grasp.

    So is classical dynamical cloning possible on S2 product spaces? The answers “yes” and “no” would both be mighty interesting: either Fenyes’ classical cloning conjecture is confirmed on compact state-spaces (the “yes” answer), or alternatively classical and quantum no-cloning theorems are shown to be more closely related than was previously conjectured (the “no” answer). Either result would be a concrete step toward a broader and deeper understanding of the marvelous interplay, both classical and quantum, between computation and physics.

  127. Scott Says:
    Comment #127 August 14th, 2011 at 6:23 pm

    Ungrateful_Person #84:

    If you’re interested in the history of complexity theory, a good place to start is this paper by Fortnow and Homer.

    As for the history of ideas leading up to the IP=PSPACE Theorem, you can’t do better than Laci Babai’s classic essay E-mail and the Unexpected Power of Interaction.

    Finally, as for “why” IP=PSPACE should hold, almost all the intuition is contained in the weaker result coNP⊆IP. Basically, it’s that
    (1) you can “arithmetize” an explicitly-given Boolean formula, reinterpreting it as a low-degree polynomial over some larger finite field, and
    (2) low-degree polynomials have powerful error-correcting properties (ultimately arising from the Fundamental Theorem of Algebra), which a prover can use to convince a verifier of the value of even an exponentially-large sum.

  128. Scott Says:
    Comment #128 August 14th, 2011 at 6:32 pm

    Ungrateful_Person #86:

    What I really want to know is that can interaction help us come up with a proof of RH or some other hitherto unproved mathematical theorem. Or all it really does is to verify whether a proof in possession of a super natural being is correct?

    Of course, two human mathematicians could conceivably prove RH by pooling their insights, even though neither one could prove it alone. Unfortunately, that sort of interaction is something that complexity theory, at least in its current state, really doesn’t know how to model. (Within the framework of complexity theory, why not just create a new mathematician who simulates both the original ones? You’ll at most double the running time… 😀 )

    Having said that, there are interesting zero-knowledge proofs that don’t require the prover to be super-powerful. A good example is the GMW zero-knowledge protocol for graph 3-colorability.

  129. Chris Says:
    Comment #129 August 14th, 2011 at 6:36 pm

    Also of interest to those interested in computability and computational complexity theory in realtion to classical physics is the work of Beggs, Costa et al.

    Can Newtonian systems, bounded in space, time, mass and energy compute all functions?
    http://www.sciencedirect.com/science/article/pii/S0304397506007481

    Embedding infinitely parallel computation in Newtonian kinematics
    http://www.sciencedirect.com/science/article/pii/S0096300305008313

    Quanta in Classical Mechanics: Uncertainty in
    Space, Time, Energy
    http://fgc.math.ist.utl.pt/doc/brussels.pdf

    On the Complexity of Measurement in Classical Physics
    http://www.springerlink.com/content/4347r31926361470/

    Comparing complexity classes relative to
    physical oracles
    http://fgc.math.ist.utl.pt/doc/joc.pdf

  130. bngrnj Says:
    Comment #130 August 14th, 2011 at 6:36 pm

    Would you see any value in exploring barriers in complexity theory in the context of reverse mathematics, with the view of possibly gaining more insight into the difficulty of proving P vs. NP or its potential independence? By this I mean finding which subsystems of second order arithmetic are necessary to establish theorems (e.g. IP=PSPACE, parity is not in AC^0) with natural, relativizing or algebrizing proofs, to see if there might be some interesting logical basis behind how these barriers limit the method of proof of certain statements. Do you think these theorems might mostly or all be provable in recursive mathematics (i.e., RCA_0), making the reverse mathematics approach not so useful?

  131. Scott Says:
    Comment #131 August 14th, 2011 at 6:37 pm

    Ungrateful_Person #88:

    What is your favorite movie, your favorite novel and your favorite piece of mathematical work?

    You’ve really exceeded your question quota, so I hope you’re grateful for this… 😀

    Favorite movie: Real Genius

    Favorite novels: Huckleberry Finn, The Mind-Body Problem

    Favorite piece of mathematical work: Dunno, maybe Cantor’s diagonal proof?

  132. helpneeded Says:
    Comment #132 August 14th, 2011 at 6:42 pm

    If I have a matrix multiplication algorithm that finishes the task in $O(n^2logn)$ how can I verify it? 5 page long paper! The idea is a bit new. I want to verify it before posting on arxiv. Also is it wise to post it on arxiv or send to a conference(if so which conference?) or better get it patented first if it works:)?

  133. Scott Says:
    Comment #133 August 14th, 2011 at 6:45 pm

    Alexander Kruel #90:

    What would you do with $1,000,000 if it were given to you on the condition that you donate it to a charity of your choice?

    I’d have to research charities much more carefully than I have before making a decision. Maybe I’d give it to VillageReach, the #1 recommended charity of GiveWell. Or if I wanted more personal involvement, maybe I’d set up my own foundation around something like math education for nerdy kids.

  134. Chris Says:
    Comment #134 August 14th, 2011 at 6:47 pm

    seems my last question sank like a lead brick, maybe you’ll allow me a second?? whats your thoughts on the nature of time and do you see any role for your area of expertise elucidating in any way this most mysterious of natural phenomena? (thats if you believe it exists at all!!) : )

  135. helpneeded Says:
    Comment #135 August 14th, 2011 at 6:48 pm

    I mean for P=NP problems verification is easy. Throw in a hard instance and watch your clock.

    Also do you think there is a mathematical obstruction that prevents classical simulation of quantum computers and quantum computers from simulating all NP problems faster? If someone where to show classical computation of Discrete log and factoring is easy would that be evidence that there could be lesser of a mathematical mystery behind QC than we currently think of? (I know we have modeled quantum mechanics. My question is a bit different.)

  136. Kimbo Slice Says:
    Comment #136 August 14th, 2011 at 6:54 pm

    My girlfriend believes in things like ghosts, reincarnation, psychics, astrology, and god. What’s the best way of extirpating these beliefs without destroying the relationship?

    p.s. do you believe it is criminal (or at least unethical) to raise a child in, say, the Mormon faith? That is, a religion with heavy time commitments and which espouses seriously irrational beliefs?

  137. kiliva Says:
    Comment #137 August 14th, 2011 at 6:54 pm

    If you read my question carefully, you can see that I don’t say that I think/feel there should be war crimes tribunal like that. I was merely exploring the possibility (and your opinion about it). Of course, ideally there should be justice for all, as crimes are not restricted to one side (neither side has much to do with me btw in Palestinian/Israeli conflict) – even in WWII, allies committed terrible crimes, that perhaps should have been examined by some tribunal. But it is a bit naive to expect justice (or to think that it exists) in such matters.

    War crimes tribunal issues are ultimately issues of power – the fact is that ICC was established in 2002, but most powerful countries – like US, Russia or China – do not admit its jurisdiction over THEIR crimes (USA even demanded third countries to sign that they would not give up US citizens to this court, while at the same time insisting that ICC has jurisdiction over those less powerful countries, i.e. rest of the World).

    Perhaps you can imagine the following situation:
    A nation in WWII gets systematically persecuted under Nazis in Europe. Laws are brought that outlaw them, and they are systematically expelled and exterminated. Hundreds of thousands die in concentration and extermination camps, and there is a successful policy of genocide that executes one third of them, expelling as many and reducing the rest to insignificant minority.

    After WWII, a historical heartland of unique religious and national significance becomes place of conflict with local muslims, wishing to wipe them out. Muslims perform terrorist actions, killing teenagers in local pubs etc. Americans put the muslim party involved on a list of terrorist organizations, condemning the terrorist attacks.

    A sequence of wars break out. The nation has superior military power in the region. Although war crimes are committed on all sides, only one side gets exclusive blame.

    After the war, a war crimes tribunal, financed by rich Arab countries like Saudi Arabia, puts blame to the select perpetrators. The nation is expelled from their heartland (reduced to a tiny minority, as hundreds of thousands of them flee). In addition, they are completely expelled from the same region in Europe which witnessed worst episodes of WWII genocide. The perpetrators of this major WWII genocide now not only deny it, but in fact celebrate it, as tens of thousands of young men wearing nazi regalia and giving nazi salute on soccer-stadium filled concerts sing songs mentioning extermination camps in positive light, and taking pride in “Max butchers” and their “work” in extermination camp slaughterhouses (where competitions were organized who would kill more of the outlawed nation). Meanwhile, as cover-up of more recent war crimes on the part of the muslims, that involves selling organs of captured civilians that are kept alive in a secret house until organs were needed, is discovered, and UN commission finally decides to take up investigation of those crimes too. The muslims respond by financing a film (fiction) about the same type of crimes, with the roles reversed.

    Sounds unbelievable? Yet this is exactly what happened to Serbs (with mentioned fights with muslim Albanians on Kosovo, and also conflicts in Croatia whose Ustashe exterminated a lot of Serbs in WWII, while Croatia expelled the remaining Serbs in the 90s). Although the worst war during breakup of Yugoslavia was in Bosnia (with conflict between Serbs, Bosniaks and Croats – all sides were warring), all wars are subject of ICTY tribunal investigations. The biggest victims are Bosniaks (who are also muslim), but then Serbs – out of 130 000 who died in these wars, 45% were Bosniaks, 35% were Serbs, 10% were Croats and 7% Albanians (roughly half of all victims are civilians), with few in other nations (Macedonia, Montenegro, Slovenia, mixed). If you count refugees, then Serbs come as worst off – out of half million Serbs from Croatia, there is less than 150 000 present now, from Kosovo 400 000 people had to move to inner Serbia, majority of them Serbs, followed by Gypsies and some other minorities; only 100 000 Serbs remain. Yet more than 80% of accused by ICTY are Serbian (from present day Bosnia, Serbia or Montenegro), followed by Croats, then Bosniaks and only a couple who are Albanian. This is how tribunals look in reality. How much this has to do with truth or justice, is another question. However, it is quite clear that it has a lot to do with power.

  138. Scott Says:
    Comment #138 August 14th, 2011 at 7:10 pm

    OK, I’m going to sleep again.

    Remember, please don’t post new questions after 9PM EST!

    I’ll clear the backlog of questions from before that point when I wake up.

  139. Len Ornstein Says:
    Comment #139 August 14th, 2011 at 7:23 pm

    Scott:

    About comment #99 or so, your server began indicating to me that it was unavailable, after I submitted my question, but apparently none the less accepted my submission. So, unfortunately, multiple attempts produced repeats of the question.

    It looks like maybe something cancelled your answer during that same period – or perhaps you chose to skip it 😉

  140. razvan Says:
    Comment #140 August 14th, 2011 at 7:30 pm

    Let’s say you have an undergrad who’s quite talented but lacks confidence and he wants to work on a research question. So you want to throw a softball his way, give him an easy thing to solve, to show him that it’s possible. What would it be?

    In other words, people ask you a lot about difficult questions, but I’m asking for the opposite: what’s the easiest, natural, open question you can think about?

  141. razvan Says:
    Comment #141 August 14th, 2011 at 7:39 pm

    Intuitively, decompiling is hard (i.e., looking at a “low-level” description of a computer program and inferring how an equivalent “high-level” representation, in a language with more sophisticated instructions looks like).
    What theorems/subfields of CS, if any, support this intuition?

  142. razvan Says:
    Comment #142 August 14th, 2011 at 7:51 pm

    What’s your favourite European CS research? (fields, people, articles, universities, whatever seems remarkable in Europe)

  143. rrtucci Says:
    Comment #143 August 14th, 2011 at 7:52 pm

    I believe it was Pancho Villa who said, as his final dying words: “tell then that I said something interesting”,
    or Spanish words to that effect.

    As this marathon answering session comes to a close, my feeble mind cannot come up with any good questions. Scott, please tell them that I asked something interesting.

  144. PeterM Says:
    Comment #144 August 14th, 2011 at 7:56 pm

    I am not a complexity theorist but I am trying to understand some aspects of it. One of these is the known barriers of proving P vs NP. An impression I got that these points toward a lesson that a successful attempt to separate P from NP must be very specific to the complexity classes involved.
    A comment (#16) you made on your P vs NP for Dummies post (https://scottaaronson-production.mystagingwebsite.com/?p=459) seems to confirm this impression in a very strong form.
    Namely you say that there could be a sort of classification of the (essentially different types of) possible polynomial time algorithms into finitely many classes.
    (In which case a separation could work by checking these one by one)

    This seems to be a very interesting and bold suggestion and even formulating it properly seems to be a very serious goal.

    On the other hand, I have a gut feeling level intuition that no such classification should exist and I would be curious to hear if you had some sort of counterargument.

    The intuition is this: of course there are many classification theorems in mathematics. What makes algorithms different for me is that I feel they are flexible enough to faithfully represent many brilliant ideas. On the other hand we KNOW
    that proving theorems is a never ending adventure, so even if this classification of algorithms is done there still will be new and new theorems using new and new ideas. And still, given that classification, we could safely say in advance that “no, none of these new ideas contain anything which could be somehow translated to a new algorithm (at least to an effective one).” I find it difficult to believe.

    So my question is if you had some intuition against the above?

  145. Arun Says:
    Comment #145 August 14th, 2011 at 8:46 pm

    Sorry I’m late to the party. I hope you’ll read this and answer it anyway.

    I know this isn’t your field, but I like asking smart people questions that aren’t in their field.

    Is the universe infinite or just really really big? Why does this question matter?

  146. Ungrateful_Person Says:
    Comment #146 August 14th, 2011 at 10:37 pm

    Scott #133

    Thanks a lot for your response. I have always been grateful to you for your wonderful blog. You rock!

  147. Scott Says:
    Comment #147 August 14th, 2011 at 11:49 pm

    OK, the fallible oracle is back!

  148. Scott Says:
    Comment #148 August 15th, 2011 at 12:02 am

    Steve Flammia #91:

    What were your three favorite quantum information theory results in the last year?

    That’s actually the hardest question I’ve gotten so far!

    To answer it, I took up your suggestion of looking at SciRate, which I’d never tried before and really like (especially because my own papers do amazingly well there 😉 ).

    Let me list three papers from the SciRate page, one of which I’ve read and know is great, and two of which I feel guilty for not having read (I’ll let you guess which is which!):

    1107.2939
    Title: Longer-Baseline Telescopes Using Quantum Repeaters
    Authors: Daniel Gottesman, Thomas Jennewein, Sarah Croke

    1011.2751
    Title: A subexponential-time algorithm for the quantum separability problem
    Authors: Fernando G. S. L. Brandao, Matthias Christandl, Jon Yard

    1107.5347
    Title: Improving Quantum Clocks via Semidefinite Programming
    Authors: Michael Mullan, Emanuel Knill

  149. Scott Says:
    Comment #149 August 15th, 2011 at 12:32 am

    semafors4 #92:

    On a political compass where do you stand:

    1. On economic scale, are you more left or right
    2. On social scale, are you more authoritarian or libertarian
    3. If you have any test scores related to this, what are they?

    I just took the quiz here, and here were my results:

    Left/Right: 4.12 out of 10 to the left
    Libertarian/Authoritarian: 1.51 out of 10 to the libertarian side
    Foreign Policy: 1.13 out of 10 to the interventionist (“neo-conservative”) side
    Culture: 4.35 out of 10 to the “cultural liberal” side

    However, I’m not sure how much to read into these scores, since they were obtained by averaging together in some cases wildly-“divergent” views. (Examples: pro-marijuana legalization, pro-gay rights and abortion rights, pro-public TV, pro-death penalty, pro-capitalism and innovation, anti-protectionist, pro-high taxes for the rich, pro-minimum wage laws, conflicted about many other social welfare policies, pro-strong gun regulations, pro-strong foreign policy)

  150. Shila Says:
    Comment #150 August 15th, 2011 at 1:08 am

    why don’t you have a good understanding of Design of gadgets for NP-completeness reductions?!

  151. Scott Says:
    Comment #151 August 15th, 2011 at 1:22 am

    serialmoth #94:

    1. What do you think about Richard Lipton and company again rising Deolalikar from the dead on their blog?

    I think it provided an important opportunity to reminisce about one of the most glorious and lasting episodes in the history of our field. Indeed, I think that every year from now on, the theory community ought to celebrate the month of August as “Deolalikar Month.”

    2. Did you read last year’s shredding into pieces of this paper and what do you think about it?

    Uhh, did you read my blog back when it was happening?

    What I think about it is: where are my mad props for having been right from the beginning? Huh? 😉

    3. Do you think the whole infamous episode was positive (due to publicity) or negative for the TCS community?

    I’m still not sure! It was incredibly interesting sociologically. To me, one thing the episode demonstrated is that, contrary to the stereotype of TCS researchers as “arrogant elitists,” many TCS researchers were willing to bend over backward to be generous, dropping everything else they were doing to study a proof attempt that passed the barest threshold of sanity. (One particularly generous and foolish blogger even offered Deolalikar $200,000 if his proof turned out to be right!)

  152. Scott Says:
    Comment #152 August 15th, 2011 at 1:53 am

    Len Ornstein #99:

    Do you think it’s important that the public and policy makers understand the difference between typical, deductive, axiomatically-derived, ‘eternal’ ‘absolute truths’ of logic and math … and the inescapable – often-sloppy but improvable – residual uncertainties of the ‘facts’ produced by the inductive approach to provisional, empirical ‘truth’ (including that of all scientific ‘knowledge’)? If you agree that it’s important – and largely ignored, even in the education of most scientists and mathematicians – (briefly) ‘how’ should ‘we’ try to fill this educational gap?

    Well, it seems obvious that 400 years after Galileo, many people still don’t “get” empiricism. They still operate in a black-or-white mode where either there’s a metaphysical “proof” of X, or if there’s no such proof, then you’re free to believe not-X if it makes you happier. We see this where X = evolution, quantum mechanics, anthropogenic climate change, the effectiveness of modern medicine, the ineffectiveness of psychics…

    Having said that, it’s not clear to me that trying to educate people explicitly about rationalist versus empiricist philosophy is the best way to tackle this problem. After all, in their ordinary lives, almost no one operates in the black-or-white rationalistic mode: indeed, those who do are judged by others to be disturbed and neurotic. So, if people were more comfortable with science in general—if science were less foreign and exotic to them—then they’d tend to realize on their own how silly it is suddenly to switch into “metaphysical rationalist mode” as soon as the subject changes to science.

    If you want more discussion of rationalism vs. empiricism—and who doesn’t?—see this recent CV post by Sean Carroll.

  153. CrankyMcCrank Says:
    Comment #153 August 15th, 2011 at 1:56 am

    I would like to rephrase my question in comment #124 into
    “Have you ever invested some time in trying to attack the P vs NP question directly?”. Maybe “Have you ever gave up…” sounds a bit misleading. Sorry english is not my native language. I wanted to write “Have you ever wasted some time…” at first, but it seemed a bit inappropriate 🙂

  154. Scott Says:
    Comment #154 August 15th, 2011 at 2:05 am

    reader from Istanbul #100:

    1- Computers with CTCs which are just 1-bit wide have recently been shown to be equivalent to computers with postselection, and so PP=PostBQP=BQP_{CTC1}. Since BQP_{CTC}, i.e, the class of languages recognized by polynomial time quantum computers with polynomially wide CTCs, equals PSPACE, if PP doesn’t equal PSPACE, there must be an intermediate width of the CTC beyond which the time-traveling bits start adding more power to the machine. What’s your guess about this intermediate function, and why do you feel so?

    Interesting … I would guess that with more than O(log(n)) bits in the CTC, you already get more than PP, but that you don’t get all the way up to PSPACE until you have nΩ(1) bits. Understanding exactly what happens in the middle would be a nice project for someone.

    2- Is there a CTC model other than Deutsch’s which is simple enough that CS people can understand and nontrivial enough to be interesting that you think deserves to be given the same treatment that you gave to Deutsch’s?

    There are already two CTC models other than Deutsch’s that have been studied from a CS perspective: first, the one of Bennett et al. (based on, as I’d put it, “defining CTCs out of existence” 🙂 ), and second, the one of Lloyd et al. (based on “postselected teleportation”). The former model gives you some subclass of BQP/qpoly, while the latter gives you PP. For my comments on those models, see Section 10 of my philosophy paper.

  155. Scott Says:
    Comment #155 August 15th, 2011 at 2:07 am

    Luca #102:

    What’s your favourite CS-theory/math book and why do you love it?

    I’ll have to go with Computational Complexity by Papadimitriou, simply because it’s the one I cut my teeth on.

  156. Scott Says:
    Comment #156 August 15th, 2011 at 2:08 am

    Anon #103:

    Has the “Physics for Doofuses” column been discontinued because you’re no longer a doofus?

    No, I’m still a doofus, just a busier doofus than before.

  157. Scott Says:
    Comment #157 August 15th, 2011 at 2:14 am

    Vadim P #108:

    you mentioned that MIT Press was publishing a book based on you your Quantum Computing Since Democritus lectures. Is it still planned? Any ETA?

    Firstly, it’s Cambridge University Press, not MIT Press.

    Secondly, I have good news: with incredibly-able assistance from my student Alex Arkhipov, we’re finally revising the manuscript, and it’s scheduled to come out sometime in 2012.

  158. Scott Says:
    Comment #158 August 15th, 2011 at 2:30 am

    AmateurBlogReader #112: Sorry, I must have missed your question before.

    If in attacking P vs NP, researchers fix their sight on a particular NP hard problem, e.g. generalized TSP and try to reason about the particular structure of the problem, are the oft quoted barriers to proofs of P vs NP the obstacle or is there something else?

    It’s certainly possible that you could find some structure in a particular NP-complete problem that would let you evade the relativization, algebrization, and natural proofs barriers. On the other hand, right now the issue is not that there are great ideas for proving P≠NP, but no specific NP-complete problems known with the right structure to implement those ideas: rather, it’s a lack of ideas.

    Right now, we don’t have any superlinear lower bound for any “natural” NP-complete problem, although we do have time-space tradeoffs: for example, we know that any no(1)-space algorithm for SAT also requires at least ~n1.7 time.

    Of course we can use the Time Hierarchy Theorem to get arbitrary polynomial lower bounds for “unnatural” NP-complete problems (and even for P problems; see my comment #25 in this thread).

  159. Job Says:
    Comment #159 August 15th, 2011 at 2:34 am

    I’m always late to these things.

    Consider the following problems, for some property Z.

    Let P(x), for some graph x (of n nodes), be the set of all possible subgraphs of x.
    Let C(y), for some set of graphs y, be the graph resulting from concatenating n members of y, according to some concatenation process (e.g. concatenate the binary representation of each graph and reinterpret as a graph).

    Given a graph G of n nodes, does a member of P(G) contain property Z?
    Given a graph G of n nodes, does a member of P(C(P(G))) contain property Z?
    Given a graph G of n nodes, does a member of P(C(P(C(P(G))))) contain property Z?
    and so on…

    If property Z describes “cliqueness” then the first problem is the clique problem and NP-Complete. The remaining problems seem to get more difficult as we go, but the question is: are all of these problems also in NP?

    If property Z can be polynomially verified, then a valid certificate for the second problem would be:
    – the locations of the n subgraphs of G that were concatenated
    – the subgraph that has property Z

    A valid certificate for the third problem would be:
    – the locations of the n subgraphs of G that were concatenated
    – the locations of the second n subgraphs that were concatenated
    – the subgraph that has property Z

    These look to be polynomially verifiable, but seem to get extraordinarily difficult, though possibly still with (very large) polynomial time solutions.

  160. Sniffnoy Says:
    Comment #160 August 15th, 2011 at 2:52 am

    No, decision problems aren’t that much easier to handle, and indeed these days people talk about other types of problems (e.g., sampling and search problems) plenty often. On the other hand, when you’re comparing different complexity classes, it helps to have a uniform standard.

    My point is, since decision-problem stuff seems to often really just be function-problem stuff specialized to the case of decision problems because that’s how people like to talk, wouldn’t it make sense to generally talk about search problem classes and only specialize to decision problems when necessary? I mean, this seems to be kind of what people do, except that since the convention is that short names denote decision problem classes, people say (e.g.) BQP when of course they’re really talking about FBQP. And most people know they really mean FBQP, except sometimes someone actually reads the definitions and gets confused! If someone had just said “FBQP with FBQP subroutines is still FBQP” instead of “BQP with BQP subroutines is still BQP”, the whole episode would have been averted… I mean, it kind of boggles me that Dick Lipton would get confused about that, but it doesn’t surprise me that people in general would get confused about it. (Or perhaps F should be replaced with… whatever.)

    (I guess search problems still aren’t the greatest generality since those exclude sampling problems… but there ought to be a way to combine those into one sort of problem, right? And ISTM everything ought to be able to be described as some sort of combination of the two…)

  161. domotorp Says:
    Comment #161 August 15th, 2011 at 2:53 am

    @Lukasz Grabowski and reader from Istanbul:

    2) I was once told that the class logspace is equal to the class of languages recognizable by read-only Turing machines with multiple readers. Do you know a reference for that?
    ————-

    Of course this is true only if the readers cannot leave the original input. If they can, then they can simulate any Turing machine!

  162. Scott Says:
    Comment #162 August 15th, 2011 at 3:46 am

    captiveted #113:

    1. Are you a Zionist? To what extent you identify with Jewish nationalism?

    Now that Israel exists, it seems strange to have to call yourself a “Zionist” as a positive ideal. So for example, are you a “Spanishist” if you feel that the nation of Spain should not be violently destroyed, most of its citizens either murdered or expelled?

    But yes, I would say that I support the ideals of Zionism. I think that the arguments were already strong when Theodor Herzl made them in Altneuland in 1902 (of all utopian novels ever written, probably the one whose vision came closest to being realized), and that they became essentially unanswerable after the Holocaust.

    Having said that, it’s worth noting that my own personal contribution to the Jewish population of Israel currently stands at -1 (i.e., Dana).

    2. Are you a pacifist, or a militant? Do you support Iraq invasion? What is your opinion about Vietnam war?

    I’m not comfortable calling myself either a “pacifist” or a “militant”: I take the commonsense position that war is terrible and sometimes unavoidable, and that any particular military action (or proposed action) should be judged on its merits.

    I think the Iraq occupation was horrendously mismanaged. I certainly had no moral qualms about overthrowing Saddam, and I think that maybe the invasion could have been a net good had the subsequent occupation been competent.

    My feelings about the Vietnam war are actually similar: I understand the US’s motivations for getting involved in the first place; the Communists really were trying to take over the world, and we were fighting Russia and China in various proxy wars rather than directly. The problem came later, with the total indifference of LBJ and then Nixon (and McNamara and Kissinger, etc.) to the facts on the ground, and their lies to the American public.

    3. Are you for death penalty? Abortion?

    I’m fine with the death penalty in principle, although I think the way it’s been implemented in practice has often been both wasteful and unjust.

    As for abortion, I think the compromise made in Roe v. Wade was quite reasonable (though after 40 years of hysterical anti-abortion activism, it might be hard to remember that it was a compromise!).

  163. Scott Says:
    Comment #163 August 15th, 2011 at 3:53 am

    Sniffnoy #160: You’re probably right, but even if so it’s way too late to change the conventions—just liek thu pepul hu tri tu reform Inglish speling ar wasting their taym.

    And besides, it’s not all bad: very often we do want to talk about decision problems!

  164. Steve Huntsman Says:
    Comment #164 August 15th, 2011 at 7:27 am

    1) Do you know of any nontrivial quantum algorithms whose intrinsically quantum steps are not essentially reducible to a Fourier transform, quantum walk, or quantum simulation (without invoking the cop-out claim that *every* quantum algorithm is a quantum simulation)?

    2) I have seen results (e.g., by R. J. Clark) that seem to day that in general, obtaining a result such as an energy gap with log N bits of precision requires at least O(N) gates. Assuming quantum computers are not used for factoring (because of the eventual emergence of post-quantum cryptography and the lead time for its deployment) and that quantum walks or other algorithms with significant power do not match up with significant utility, what does this restriction mean for the ultimate future of applied quantum computation?

    3) Naive applications of the Born-Oppenheimer approximation for electronic structure calculations actually hinder the performance of quantum simulation relative to brute-force methods for systems of size likely to be addressed in the foreseeable future. That said, what do you make of the possibility for exploiting gauge symmetries (specifically, the structure of U(n) magnetic monopoles) in the BO approximation for quantum simulation?

  165. Steve Huntsman Says:
    Comment #165 August 15th, 2011 at 7:29 am

    PS—I know I’m late, so I don’t expect answers.

  166. James Says:
    Comment #166 August 15th, 2011 at 8:04 am

    That was great! Maybe one last…

    Which other bloggers would you particularly like to see run a question marathon?

  167. Joshua Zelinsky Says:
    Comment #167 August 15th, 2011 at 9:27 am

    If you’re willing to consider sublinear complexities, then we know that there exists an n vs. n0.753 separation for a total function (game-tree evaluation), and even an n vs. O(1) separation for a promise problem (e.g., whether the input string contains >2n/3 or <n/3 ones). So let’s assume that we’re talking about superlinear complexities only.

    This confuses me. I see how one can get this problem in log n time but not O(1). The idea in question is to pick a random bit from the input string and just return that, yes? In that case, to specify a random such bit one needs to get log_2 n random bits so you can specify a random element of the input. Or is there something I’m missing?

  168. Dimitris Leventeas Says:
    Comment #168 August 15th, 2011 at 10:36 am

    Psychology studies human mind, while TCS studies computation. Do you think these two fields could eventually converge?

  169. Jr Says:
    Comment #169 August 15th, 2011 at 11:57 am

    Are you familiar with the idea that our sexual preferences are
    socially constructed, not biologically determined? If so, what do you think about it?

  170. Scott Says:
    Comment #170 August 15th, 2011 at 1:21 pm

    oligogal-c #114:

    Have you ever experimented with (i.e. tried) drugs, and if you have, what drugs have you tried?

    I visited the coffeeshops in Amsterdam a few times, where I sampled some “weed muffins” and “space smoothies” (I quickly learned that I hate inhaling any kind of smoke, regardless of what’s being burned). I enjoyed the experience, and actually benefited a lot from it—not because it led to any scientific insights (long story short: it didn’t 😀 ), but because it helped me cope with some personal problems.

    I was extremely uptight and nerdy back then, and I knew it, and I knew it was preventing me from doing things I wanted to do, and it frustrated me greatly. So, paradoxically, getting high played a major role in helping me understand what the world must look like to a “normal, neurotypical” person. On the other hand, now that I’ve become more “normal” myself (or at least, learned how to simulate a normal person when needed), getting baked is not something that I feel the desire to do again (well, no more than maybe once per decade).

    I’ve never tried cocaine, acid, mushrooms, or anything like that and don’t intend to.

    What do you think about legalization of marijuana?

    300% for it.

    What is your favorite alcoholic beverage (if any)?

    Grasshoppers (and chocolate liqueur).

  171. Scott Says:
    Comment #171 August 15th, 2011 at 1:36 pm

    LonePeep #116:

    If you had to pick two or three papers to be verified using Isabelle/HOL/Coq or some other computer assisted theorem prover, which would they be and why?

    To be honest, I can’t think of any paper that I see a pressing scientific need to verify using a computer-assisted theorem prover—even supposing that I had doubts about some paper, it seems like a massively-inefficient way to resolve those doubts.

    On the other hand, there are countless results that it would be cool to verify in this way! Like, how about the PCP Theorem? Or pretty much any result in complexity theory—even something simpler like Cook-Levin or the Time Hierarchy Theorem? (I’m not aware of any automated verification of any complexity-theory result.)

    For more of a “challenge,” how about the Classification of Finite Simple Groups? 😉

  172. Scott Says:
    Comment #172 August 15th, 2011 at 1:41 pm

    Joshua Zelinsky #167:

    This confuses me. I see how one can get this problem in log n time but not O(1). The idea in question is to pick a random bit from the input string and just return that, yes? In that case, to specify a random such bit one needs to get log_2 n random bits so you can specify a random element of the input. Or is there something I’m missing?

    Yeah, good point—it depends on whether you’re working in a “unit-cost model” or a model that accounts for bit operations. If the latter, then you indeed need ~log2n steps.

    The reason I forgot to mention that is that, when we talk about sublinear-time algorithms, usually (for convenience) we only count the number of accesses to the input, and ignore the other steps. (For the other steps hardly ever add more than a log(n) factor anyway!)

  173. Scott Says:
    Comment #173 August 15th, 2011 at 1:43 pm

    LonePeep #118:

    if you had to pick one or two mathematics classes … that have surprisingly or unexpectedly come in handy during your research career, which would they be?

    Linear algebra and abstract algebra. (Also, if it counts, numerical analysis.)

  174. Scott Says:
    Comment #174 August 15th, 2011 at 1:50 pm

    Luke #121:

    Do you think there’s a chance computers will find a proof of PvNP before humans do? What sort of probability would you assign to that?

    Sure, there’s a chance. But I don’t even know how to assign a probability—it’s really a situation of “Knightian uncertainty” for me.

    The consequences of knowing for sure P!=NP might be smallish (most everyone proceeds with the assumption P!=NP), but what sort of impact would you guess knowing how to *prove* P!=NP would have?

    As I’ve said many times before, P≠NP is “not about the destination but the journey.” I’d expect any proof to lead to a profound new understanding of efficient computation—for example, to the discovery of many new and important problems that are solvable in polynomial time.

  175. Scott Says:
    Comment #175 August 15th, 2011 at 2:12 pm

    Amirali #123:

    What do you think of Obama? Predictions for 2012 elections?

    I’ve been and remain a strong supporter of President Obama; I consider him the best president since I was born.

    On the other hand, I confess to being disappointed that he hasn’t fought the Republicans nearly as hard as I would’ve hoped, on crucial issues like the need to raise taxes on the rich to ensure the country’s financial stability. He’s pursuing a “lose-lose” strategy: repeatedly compromising with a party that has zero interest in compromise, thereby failing to get his supporters what they want and looking weak and hurting his reelection chances.

    As for those reelection chances, Intrade is currently giving him a 52.2% probability, but that seems too low to me. Alan Lichtman, the guy who’s used a 13-variable perceptron model to correctly predict every presidential election since 1980 (and retrodict every election before that), clearly predicts Obama will win, and that was before the killing of bin Laden. And all the Republican contenders seem pathetic. So, despite Obama’s self-sabotaging behavior, I’ll give him maybe a 68% chance of reelection.

  176. Jr Says:
    Comment #176 August 15th, 2011 at 2:14 pm

    Do you think it makes sense to judge some religions as worse, from a human rights point of view, based on what their holy scriptures say? Or do you think scriptures are so consistently ignored whenever people want that it does not matter?

  177. Scott Says:
    Comment #177 August 15th, 2011 at 2:18 pm

    CrankyMcCrank #124:

    Have you ever gave up some time to find a proof for P not equal NP? What was your strategy?

    Yes, when I was 15 years old. My “strategy” was to relax 3SAT to a continuous optimization problem, then use some sort of continuous math (definitely involving multivariable calculus) to prove that the landscape of local minima would be too complicated for any polynomial-time algorithm to navigate. I considered it a brilliant idea that no one had ever thought of before.

  178. Scott Says:
    Comment #178 August 15th, 2011 at 3:31 pm

    Chris #125:

    separation of complexity classes relative to some physical oracle as in the work of Beggs, Costa et al. was what i was talking of

    Well, if you wanted to prove a separation between P and NP relative to a “physical oracle,” you’d first need a clear definition of what the “physical oracle” was—but then it wouldn’t be a physical oracle at all, just another well-defined mathematical oracle!

  179. Scott Says:
    Comment #179 August 15th, 2011 at 3:33 pm

    John Sidles #126:

    Scott, what are your three favorite yellow books?

    Sorry, I don’t read yellow books! (Indeed, that’s how I know I’m not a mathematician.)

  180. Scott Says:
    Comment #180 August 15th, 2011 at 3:43 pm

    bngrnj #130:

    Would you see any value in exploring barriers in complexity theory in the context of reverse mathematics, with the view of possibly gaining more insight into the difficulty of proving P vs. NP or its potential independence?

    There has been significant work along those lines. See in particular:

    Relativizing versus Non-relativizing Techniques: The Role of Local Checkability, by Arora, Impagliazzo, and Vazirani
    (reinterprets “relativizing proofs” as “proofs that only invoke Cobham’s axioms for P plus two additional axioms”)

    An Axiomatic Approach to Algebrization, by Impagliazzo, Kabanets, and Kolokolova
    (reinterprets algebrization along similar lines to the above AIV paper)

    Section 4 of my survey article Is P Versus NP Formally Independent?, which talks about the work of Razborov and others getting formal independence implications (often conditional on pseudorandomness assumptions) from the natural proofs barrier.

    The above work is all extremely cool, and certainly gives us more insight into the three barriers. Whether any of it helps point us in the direction of actual lower bound proofs is another question…

  181. Scott Says:
    Comment #181 August 15th, 2011 at 3:49 pm

    helpneeded #132:

    If I have a matrix multiplication algorithm that finishes the task in $O(n^2logn)$ how can I verify it?

    Dude, there’s probably a bug in your algorithm.

    If you can’t find it yourself, my suggestion would be to offer to pay a grad student a few hundred bucks to find it for you. For more about that, see this thread on CS Theory StackExchange.

  182. Scott Says:
    Comment #182 August 15th, 2011 at 3:50 pm

    Chris #134:

    whats your thoughts on the nature of time and do you see any role for your area of expertise elucidating in any way this most mysterious of natural phenomena?

    See Section 10 of my philosophy paper, or my post Time: different from space.

  183. Scott Says:
    Comment #183 August 15th, 2011 at 4:04 pm

    helpneeded #135:

    Also do you think there is a mathematical obstruction that prevents classical simulation of quantum computers and quantum computers from simulating all NP problems faster?

    Well, I think that BPP≠BQP and that NP⊄BQP, and also that both of those statements are true for reasons that we don’t fully understand yet (in other words: that, yes, there exist “mathematical obstructions” to their falsehood!).

    If someone where to show classical computation of Discrete log and factoring is easy would that be evidence that there could be lesser of a mathematical mystery behind QC than we currently think of?

    Yes, it could be such evidence. For more see Section 8.1 of my philosophy paper.

  184. helpneeded Says:
    Comment #184 August 15th, 2011 at 4:17 pm

    Scott #181: That is for P!=NP. Is MM, a difficult problem of such magnitdue? Why do you think there is no elementary approach to the problem?

  185. Ungrateful_Person Says:
    Comment #185 August 15th, 2011 at 4:58 pm

    It is wonderful to know that you knew NP Completeness when you were only 15. That makes me cower in fear in a small corner (I mean what was I when I first heard of it – 23?). Am just curious if you care to share what other theorems were you aware of that people typically learn in their senior years when you were around this age?

  186. Joshua Zelinsky Says:
    Comment #186 August 15th, 2011 at 5:25 pm

    Scott, thanks. That clarifies things.

  187. Sid Says:
    Comment #187 August 15th, 2011 at 5:51 pm

    1) If you could choose, would you want P=NP or P!=NP?

    2) A while ago, you listed the fact that we don’t have any generic heuristics to obtain exponential speedups in practice as an argument against P=NP. But can’t the same argument be applied to human-level AI since there too we don’t have a set of techniques that can simulate that level of intelligence. Now any such techniques for the latter are likely to be very varied and complicated (which is probably why we haven’t found them) but the same can be true for the former…

    3) Is there any research on doing proof-length estimates of the following sort – suppose we know X,Y and Z then starting from that, a proof of the Riemann Hypothesis will by atleast of length l. Then collecting a list of theorems, etc. that are common knowledge one might be able to estimate how long the proof of the Riemann Hypothesis by a human might be. Depending how the estimate is done, one might even be able to elicit some knowledge as to how to go about such a proof.

  188. Kimbo Slice Says:
    Comment #188 August 15th, 2011 at 6:12 pm

    Since it seems the Q and A isn’t over, I guess I’ll ask a question. How do you justify the rewards and freedoms you enjoy as an academic at a premier institution given that a large part of your success is due to the randomness of your birth–that you are, genetically, smarter than most people. I realize that there is such a thing as hard work, but that is probably a function of genetics as well. Please don’t get sidetracked by the fact that this question could be put to many if not most people in some respect. I’m merely asking if, as you enjoy a fine meal in an exclusive Boston eatery, you ever feel as though there is some justice problem with your indulgence.

  189. Vijay Krishnan Says:
    Comment #189 August 15th, 2011 at 8:15 pm

    @Kimbo Slice (188):

    Yes, genes explain ~50% of the variation in adult personality and intelligence. You can hold one of two stances:
    1. You like in a society where people like Scott thrive and do justice to their potential and serve as role models for much of the population. You have taxation etc. and a system that ensures that most people have a minimum (but not equal) standard of living.

    2. You live in a society where everyone is a slave. People aren’t permitted to leave the aforesaid country to one that would respect their talents; the government somehow figures out what your true potential is when you are a child and sets up an incentive structure such that if you were super smart and consequently likely to become rich, successful, famous, respected etc. it would start you off with a huge negative handicap (you need to explain to me how this estimation of adult aptitude during childhood will be accurate, since this will create extremely perverse incentives of parents ensuring that their children are as “dumb” as possible during any possible measurements, and possibly dumb down society and the quality of the workforce later). The nature of the negative handicap on such individuals would be such that only if they created untold wealth or created huge contributions to science, technology or society, they would get a post-tax government salary that equals the mean salary in the country. If your net contribution to society is much lower than your potential (but still way higher than the average person), then the government would confiscate all your money in taxes and force you to be homeless and push you to the brink of starvation. Given that high IQ people have a disproportionate contribution to society and the fact that IQ is highly heritable, you will also need to ensure by fiat that high IQ people multiply and create more slave babies for the state (since in the absence of that it is very likely that sheer depression and despondency among other things will cause the higher IQ people to breed even slower compared to the rest of the population than what they are doing now).

    It has been obvious to me for quite a while now that if you apply modus ponens enough times on your premise, you also have to swallow the fact that what you want is a totalitarian society with no human liberties whatsoever. What I have listed above is the best case scenario! In practice, I am sure the incentive structures will get gamed; enough high IQ people will manage to leave the country in question and the scenario would be far more bleak than (2) above, which already is quite bleak and depressing.

  190. Vijay Krishnan Says:
    Comment #190 August 15th, 2011 at 8:29 pm

    Of course it goes without saying that (2) is a necessary consequence of the reasoning of @Kimbo Slice, because the alternative of a government mandated cap on money, respect, fame etc. will only backfire and prevent high contributors from contributing anything of note to society. This piece has been pretty well explained by Paul Graham in:
    http://www.paulgraham.com/inequality.html

    I build (2) upon the premise that society would collapse if smart people were disincentivized from doing justice to their potential. The only way to counter is de-factor slavery where smart people are still extremely incentivized to perform to their potential (current the incentives is fame, money, power, respect etc.) and in scenario (2) the incentives will change to avoiding starvation and homelessness.

  191. John Sidles Says:
    Comment #191 August 15th, 2011 at 8:56 pm

    Kurt Vonnegut’s now-classic short story Harrison Bergeron (1961, available on-line) nicely summarizes both edges of Vijay’s commentary. There is also Cicero’s two-sided maxim Assiduus usus uni rei deditus et ingenium et artem saepe vincit (“Constant practice devoted to one subject often outdues both intelligence and skill”), Cordwainer Smith’s meditation upon the practical perils of oracles in his short story Alpha Ralpha Boulevard, and Austin Grossman’s hilarious description of “malign hypercognition disorder” (evil genius syndrome) in his comedic novel Soon I Will Be Invincible.

    The world that Vijay describes would be a world largely without tragedy, comedy, heroes & heroines, or villains in their infinite variety … there would be little to hope for and yet no reason to despair … Jim, Huck, the King, and the Duke all would stay-at-home and live soberly … and so it’s not clear that this world would be an upgrade.

  192. Scott Says:
    Comment #192 August 15th, 2011 at 10:03 pm

    Kimbo Slice #136:

    My girlfriend believes in things like ghosts, reincarnation, psychics, astrology, and god. What’s the best way of extirpating these beliefs without destroying the relationship?

    That might be the most interesting question I’ve gotten so far! Alas, having been in similar situations myself, I don’t know the answer. Indeed, my guess would be that you’re never going to bring her around through rational persuasion: if she were amenable to rational persuasion on these subjects, then she would’ve already abandoned the beliefs you mention a long time ago.

    So, I think the first question you need to answer is this: would you still want to continue the relationship, even if you knew for sure that, for whatever reasons, she would never adopt a post-Enlightenment worldview?

    If the answer is no, then break up with her. You could look for a new girlfriend by, for example, propositioning women in the elevators at atheist/skeptic conventions. 😉

    If the answer is yes, on the other hand, then the best thing I can suggest is to adopt an attitude of amused, ironic indifference. So for example, suppose your girlfriend starts talking about palm reading. Then you would say: “y’know, this might surprise you, but I actually think there’s some truth to palm-reading. A friend once taught me how to do it at summer camp, and I gained a lot of insight from it. Here, let me try reading your palm! OK … ohhh, very interesting. You see this line here? This one is telling me you’re someone who knows, at a subconscious level, that your boyfriend is always right… ” [you take it from here]

    do you believe it is criminal (or at least unethical) to raise a child in, say, the Mormon faith? That is, a religion with heavy time commitments and which espouses seriously irrational beliefs?

    While I’m very interested in children’s rights, to be honest I can’t think of any way to craft a law along the lines you suggest that would avoid terrible consequences. For example: I think it should be a criminal offense for parents to teach their children that quantum mechanics is about “light being both a wave and a particle,” rather than about generalizing probability theory to involve minus signs. Should I have the authority to put parents behind bars if they persist in teaching their children the Copenhagenists’ mind-numbing obfuscations? 🙂

    I think the only real solution is to improve children’s rights in general. That way, parents could try to teach their children anything they wanted, but the children’s right to think differently would be sacrosanct.

  193. Scott Says:
    Comment #193 August 15th, 2011 at 11:05 pm

    razvan #140:

    Let’s say you have an undergrad who’s quite talented but lacks confidence and he wants to work on a research question. So you want to throw a softball his way, give him an easy thing to solve, to show him that it’s possible. What would it be?

    That’s a very difficult question, and (as you can imagine) something I’m constantly dealing with in practice. It depends a lot on the student—I’ve found that, if they’re not interested or motivated, then they’ll flail around even with the most softball question you can possibly give.

    So, one approach is to let the student suggest a question—when they can, that’s often the best!

    A second approach is to let them browse CS Theory StackExchange for open problems.

    A third approach is to save up any softball questions you hear about or that arise in your own work (but that, for whatever reason, you don’t solve yourself).

    For specific project ideas, see my posts Projects Aplenty or Research projects in quantum complexity theory.

  194. Scott Says:
    Comment #194 August 15th, 2011 at 11:12 pm

    razvan #141:

    Intuitively, decompiling is hard (i.e., looking at a “low-level” description of a computer program and inferring how an equivalent “high-level” representation, in a language with more sophisticated instructions looks like).
    What theorems/subfields of CS, if any, support this intuition?

    You should check out the literature on program obfuscation.

    See for example this classic paper by Barak et al. (which actually proves a negative result—though not one that contradicts the intuition you stated), or this one by Hoeteck Wee.

  195. Scott Says:
    Comment #195 August 15th, 2011 at 11:14 pm

    razvan #142:

    What’s your favourite European CS research?

    CWI in Amsterdam. I have great friends there, and have had many wonderful visits.

  196. Scott Says:
    Comment #196 August 15th, 2011 at 11:30 pm

    PeterM #144:

    I have a gut feeling level intuition that no such classification [of all possible polynomial-time algorithms] should exist and I would be curious to hear if you had some sort of counterargument.

    I share your intuition that the class of all possible polynomial-time algorithms is in some sense “infinitely rich,” and therefore we can never hope for a complete classification.

    Indeed, some people have put that forward as an argument for why we’ll never be able to prove P≠NP. But there must be some flaw in the argument (as it stands), since the “infinite richness of P” didn’t prevent Hartmanis and Stearns from proving P≠EXP!

    One possible flaw is that, as long as we’re willing to focus on a particular problem (say, an NP-complete problem), we might be able to classify all algorithmic techniques that are useful for that problem. At an extremely vague level, you could argue that that’s the hope of Mulmuley’s GCT program: namely that, by focusing on problems (like the permanent) that can be characterized by their symmetries, one can reduce the “effective search space” of algorithms that need to be considered.

  197. Guillermo Says:
    Comment #197 August 15th, 2011 at 11:32 pm

    do you own a cat ?
    what is his/her name ?

    🙂

  198. Scott Says:
    Comment #198 August 15th, 2011 at 11:47 pm

    Arun #145:

    Is the universe infinite or just really really big?

    The observable universe—i.e., the part of the universe that we can ever receive signals from—now appears to be finite, ever since the discovery of the dark energy in 1998. It has a radius somewhere on the order of 20 billion light-years (give or take a factor of 2 🙂 ).

    On the other hand, the universe itself (even forgetting about any possible other universes) might go on for quite a ways beyond that. Cosmologists don’t know today whether it’s finite or infinite, but that doesn’t necessarily mean the question is “forever beyond human understanding.”

    So for example, if a positive spatial curvature were ever discovered, that would provide strong evidence that the universe “eventually wraps around” and is finite—just like the discovery several thousand years ago of a positive spatial curvature to the earth (e.g., the fact that ships disappear past the horizon from the bottom upwards) provided strong evidence that the earth was finite.

    Unfortunately, despite high-powered searches over the last few decades, no deviation from a perfectly-flat universe on a cosmological scale has ever been found. I think it’s now known that, if the universe has a positive spatial curvature, then the radius of curvature must be at least something like 50-100 times the radius of our observable patch.

    On the other hand, note that even if the curvature of space was exactly zero on a cosmological scale, the universe could still wrap around and be finite: topology is a different issue than geometry!

    If you want to know more, you should really be asking a cosmologist like Sean Carroll rather than a complexity theorist like me. 🙂

    Why does this question matter?

    Dude, if you have to ask…

  199. Scott Says:
    Comment #199 August 15th, 2011 at 11:49 pm

    Job #159: Sorry man, your question is not only past the deadline but also way too complicated!

  200. Scott Says:
    Comment #200 August 16th, 2011 at 12:01 am

    Steve Huntsman #164:

    I’ll tackle your first question only, both because you’re past deadline and because your other two questions require way more physics knowledge than I have.

    Do you know of any nontrivial quantum algorithms whose intrinsically quantum steps are not essentially reducible to a Fourier transform, quantum walk, or quantum simulation…?

    Yes. Today we know quantum algorithms based on several other primitives, such as the Haar wavelet transform and the “Clebsch-Gordan transform” (whatever that is 🙂 ). For an example of the former, see this paper by Shelby Kimmel; for the latter, see this one by Dave Bacon.

  201. Scott Says:
    Comment #201 August 16th, 2011 at 12:03 am

    James #166:

    Which other bloggers would you particularly like to see run a question marathon?

    Pretty much any of the bloggers I read! (E.g., the ones on my blogroll to the right.)

  202. Scott Says:
    Comment #202 August 16th, 2011 at 12:10 am

    Dimitris Leventeas #168:

    Psychology studies human mind, while TCS studies computation. Do you think these two fields could eventually converge?

    Wouldn’t it be much more plausible for psychology to converge with AI than with TCS? Indeed, you could say that the field of cognitive science does represent a convergence between psychology and AI—not that the latter two aren’t also pursued separately.

    In general, while connections between fields get made all the time, it’s hard to think of any modern example of two fields “converging” in the sense that their separate identities are obliterated. Despite predictions to the contrary, quantum mechanics never obliterated chemistry as a separate field, and quantum complexity theory (strangely enough) didn’t obliterate either quantum mechanics or classical complexity theory… 🙂

  203. Scott Says:
    Comment #203 August 16th, 2011 at 12:14 am

    Jr #169:

    Are you familiar with the idea that our sexual preferences are socially constructed, not biologically determined? If so, what do you think about it?

    Yes, I’m familiar with that “idea,” and I think it’s bullshit. Among other pieces of evidence, the track record of programs that try to “convert” gays to heterosexuality is a miserable one.

  204. Scott Says:
    Comment #204 August 16th, 2011 at 12:28 am

    Jr #176:

    Do you think it makes sense to judge some religions as worse, from a human rights point of view, based on what their holy scriptures say? Or do you think scriptures are so consistently ignored whenever people want that it does not matter?

    In general, I think it makes the most sense to judge a religion (or a particular strain of a religion) by what its adherents do. Of course, what the adherents do might be strongly affected by what their scripture tells them to do (depending on the historical era, the religion, and most of all the adherent). But I wouldn’t want to prejudge that. Many, many religious people are better than their religions’ scriptures.

  205. Scott Says:
    Comment #205 August 16th, 2011 at 12:32 am

    helpneeded #184:

    Why do you think there is no elementary approach to [matrix multiplication]?

    There might be, but many extremely smart people have thought about matrix multiplication for the past 40 years. In general, if you think you’ve solved a problem of that magnitude, it’s best to adopt the humble attitude that you probably made a mistake and that the challenge is to find it. I wouldn’t do any differently myself.

  206. Scott Says:
    Comment #206 August 16th, 2011 at 12:51 am

    Ungrateful_Person #185:

    Am just curious if you care to share what other theorems were you aware of that people typically learn in their senior years when you were around this age?

    Much of what I “knew” at that age I had picked up at Canada/USA MathCamp, a wonderful program that exposes high-school kids to all sorts of very advanced math (Ken Ribet even gave a whole series of lectures there on elliptic curves and Fermat’s Last Theorem).

    On the other hand, the whole point of my story was that I only thought I knew these things well enough to do research. It would be years until I “really” understood even simple stuff like the Cook-Levin Theorem.

    On the third hand, I do think that being exposed to such concepts early was a huge help. For it meant that, when I encountered them again later, it wasn’t the first time I’d ever seen them.

  207. Scott Says:
    Comment #207 August 16th, 2011 at 12:55 am

    Sid #187:

    1) If you could choose, would you want P=NP or P!=NP?

    P≠NP. The alternative seems too flat and boring.

    2) A while ago, you listed the fact that we don’t have any generic heuristics to obtain exponential speedups in practice as an argument against P=NP. But can’t the same argument be applied to human-level AI…

    The big difference is that, in the case of AI, we already have what looks a helluva lot like an existence proof that thinking machines are possible: us!

    3) Is there any research on doing proof-length estimates of the following sort – suppose we know X,Y and Z then starting from that, a proof of the Riemann Hypothesis will by atleast of length l. Then collecting a list of theorems, etc. that are common knowledge one might be able to estimate…

    No, not that I know of.

  208. Amirali Says:
    Comment #208 August 16th, 2011 at 1:46 am

    Way passed the deadline, but a short one: Do you think the Unique Games Conjecture is true? With what level of certainty?

  209. helpneeded Says:
    Comment #209 August 16th, 2011 at 3:18 am

    Thankyou for Comment #205. I found a flaw today morning when I wokeup (without sleep). It seems fixable. I think I have fixed it. I have to do some clean up and do some simulation to see if it really throws out correct values. It turned out trickier than I hoped for (the fix) and due to that the explicit math looks messier. The odds that I have made another blunder has probably increased. I will chew on it for a while. If the symbols all align well may be someday (hopefully soon), I will release it.

  210. Steve Huntsman Says:
    Comment #210 August 16th, 2011 at 7:12 am

    @ Scott 200: After a casual glance at both of these papers, it looks very much like they invoke a QFT, albeit a nonstandard one.

  211. Pratik Deoghare Says:
    Comment #211 August 16th, 2011 at 8:45 am

    You have used word boson in your paper(The Computational Complexity of Linear Optics). Why? Only boson over which we have reasonable control is photon. Then why didn’t you just say photon?

    NOTE: I am n00b in almost everything related. 🙂
    Thanks!

  212. Jan de Wit Says:
    Comment #212 August 16th, 2011 at 9:50 am

    First question: Does EST mean Eastern Standard Time or European Summer time? 🙂

    Second question: One thing that still confuses me greatly in complexity theory is that the the relativization operator is not referentially transparant and breaks Leibniz’s Law.

    Normally, if A=B then f(A) = f(B) for arbitrary A,B and f. Somehow this fails when A and B are carefully selected complexity classes and f is the ‘relativize by an (also chosen carefully) oracle O’ operation. I.e. A=B but A^O != B^O.

    What exactly is going on here? My gut feeling is that the equality operator means something different than what I’m used to (i.e. it depends on what the meaning of ‘is’ is!) but I’m not sure.

  213. pete Says:
    Comment #213 August 16th, 2011 at 11:22 am

    Scott, since you seem to be issuing extensions all round… (and please pardon the considerable confusion no doubt implied) .. do you think it would be possible to define what constitutes a “computational process” by physical criteria alone, or know of any attempts at such a definition?

    Cheers!

  214. Scott Says:
    Comment #214 August 16th, 2011 at 12:20 pm

    Guillermo #197:

    do you own a cat ?
    what is his/her name ?

    I had a cat named “Rabbit” when I was little (a stray my mother adopted), but he died of cancer when I was 12.

    I like cats, but Dana and I do way too much traveling for it to be practical for us to have one right now. Also, I’m not particularly excited about cleaning cat shit.

  215. Scott Says:
    Comment #215 August 16th, 2011 at 12:21 pm

    Amirali #208:

    Do you think the Unique Games Conjecture is true? With what level of certainty?

    I’ll guess that it’s true with 75% probability.

  216. Scott Says:
    Comment #216 August 16th, 2011 at 12:28 pm

    Pratik Deoghare #211:

    You have used word boson in your paper(The Computational Complexity of Linear Optics). Why? Only boson over which we have reasonable control is photon. Then why didn’t you just say photon?

    Alex and I had a lot of discussion and debate about precisely that question! On the one hand, photons were obviously what we implicitly had in mind (and not, say, gluons or Higgs bosons 😀 ). On the other hand, mathematically we weren’t using any properties of photons besides the fact that they were identical bosons.

    In the end, what decided the question is that someone pointed out to us that it might also be feasible to do our experiment using quasiparticle excitations in condensed-matter systems that behave like identical bosons. (We mention that in Section 6.2.)

  217. Scott Says:
    Comment #217 August 16th, 2011 at 12:34 pm

    Jan de Wit #212:

    One thing that still confuses me greatly in complexity theory is that the the relativization operator is not referentially transparant and breaks Leibniz’s Law … What exactly is going on here?

    The right way to think about it is that relativization acts on the definition of a complexity class, not on its extension (i.e., on the actual set of languages). That’s how it can be the case, for example, that IP=PSPACE, yet there exists an oracle A such that IPA≠PSPACEA. Even though IP and PSPACE turn out to define the same class of languages in the unrelativized world, their definitions are still different, and the oracle A takes advantage of their differing definitions to separate them. The best way to understand this is to work through some actual examples.

    UPDATE: Here’s an analogy. The two phrases “the President of the United States” and “Barack Obama” both pick out the same person. However, “the President in a hypothetical world where John McCain won the election” is still the President, whereas “Barack Obama in a hypothetical world where John McCain won the election” is not. Hence we’ve constructed an oracle that separates the two. 🙂

  218. helpneeded Says:
    Comment #218 August 16th, 2011 at 12:40 pm

    Comment #217: Could you suggest some articles/examples on this relativization example where the oracle separates though the classes are the same?
    Thankyou

  219. Scott Says:
    Comment #219 August 16th, 2011 at 12:45 pm

    helpneeded #218: I can’t think of any paper that talks about it explicitly. Just try to understand the Baker-Gill-Solovay oracle that separates P and NP, and think about how that oracle would still work even if P=NP in the real world. Then enlightenment will strike.

  220. helpneeded Says:
    Comment #220 August 16th, 2011 at 12:46 pm

    Ok thankyou for the prompt response.

  221. Scott Says:
    Comment #221 August 16th, 2011 at 12:49 pm

    pete #213:

    do you think it would be possible to define what constitutes a “computational process” by physical criteria alone, or know of any attempts at such a definition?

    Sorry, this question is too vague for me. What’s the goal? I would tend to think the other way around: everything in the physical world can be regarded as a computational process (if you choose to regard it as such), but there are also computational processes (say, ones that run for 1010000 steps) that have no physical realization.

  222. Pratik Deoghare Says:
    Comment #222 August 16th, 2011 at 1:03 pm

    @Scott Thank you very much! I asked because I’m bit scared of elementary particles. But photons are good old friends. 😀

  223. Scott Says:
    Comment #223 August 16th, 2011 at 1:51 pm

    Kimbo Slice #188:

    How do you justify the rewards and freedoms you enjoy as an academic at a premier institution given that a large part of your success is due to the randomness of your birth–that you are, genetically, smarter than most people … I’m merely asking if, as you enjoy a fine meal in an exclusive Boston eatery, you ever feel as though there is some justice problem with your indulgence.

    First of all, by “exclusive Boston eatery,” do you mean Dunkin Donuts (where I had breakfast this morning), or the burrito place near Stata? 😀

    The short answer to your question is that I went through more than a decade of serious depression—during which it was obvious to me that, precisely because of the nerdy characteristics you mention, I would never have a normal social or romantic life. My state of mind at that time was well-described by the following Bertrand Russell quote:

      In adolescence, I hated life and was continually on the verge of suicide, from which, however, I was restrained by the desire to know more mathematics.

    (Someday I’d like to write more about this phase of my life—and in particular, the lessons I learned that might be helpful to other teenage nerds—but I don’t think it’s the right time yet.)

    Anyway, while the process was slow and non-monotonic, at some point life turned a corner and became pretty pleasant. Now, I don’t think for a second that the depression I went through as a teenager entitles me to be an arrogant prick today. I want to feel like I’m “giving something back to humanity”—if not by building wells in Third World villages, then at least by spending days answering random blog questions. 😀 On the other hand, what I went through does have the benefit that today I never feel guilty about any enjoyment of life that happens to come my way.

  224. Weekly Picks « Mathblogging.org — the Blog Says:
    Comment #224 August 16th, 2011 at 2:11 pm

    […] Shtetl Optimized released an essay on computational complexity and philosophy — together with the yearly “ask me anything” thread Shtetl Optimized received a mind boggling 260+ comments last week. Meanwhile at the Statistics […]

  225. Rob Renaud Says:
    Comment #225 August 16th, 2011 at 2:24 pm

    What do you think about the Aaron Swartz/jstor/MIT saga? Is the guy a terrible copyright infringer, possibly destroying millions of dollars of revenue? Is he a brazen hero trying to free up academic works that rightfully belong to the world as whole from a crazy system that keeps them locked down for profit?

  226. Scott Says:
    Comment #226 August 16th, 2011 at 3:10 pm

    Rob Renaud #224: I believe that in a few decades, the world will have caught up with Mr. Swartz’s views about copyright. But given that it hasn’t yet, I wouldn’t have advised him to do what he did. Civil rights was worth going to jail for; off-campus access to jstor articles probably isn’t.

  227. Douglas Knight Says:
    Comment #227 August 16th, 2011 at 4:42 pm

    Scott @ 192,

    It seems odd to me to contrast “light being both a wave and a particle” with “generalizing probability theory to involve minus signs” or to relate either to collapse vs no collapse.

    Rob Renaud, it is not at all clear that AS was trying to pirate the material.

  228. John Sidles Says:
    Comment #228 August 16th, 2011 at 8:18 pm

    Per Scott’s answer # 25

    I don’t know of any “natural” problem (not involving large numbers in its statement) that’s known or even conjectured to require (say) n^1000 time. Whether such problems exist is of course an extremely interesting question.

    Restricting the answer to problems that are both natural and economically important, the largest exponents (known to me) are the n^7 exponents of wave-function methods in quantum chemistry, in which n is the number of electrons. For an enjoyably accessible discussion of these methods, see Walter Kohn’s now-classic PRL article Density Functional and Density Matrix Method Scaling Linearly with the Number of Atoms (1996) and also Kohn’s Nobel Lecture (1998). A highly recommended recent survey is the PCCP article Advances in methods and algorithms in a modern quantum chemistry program package (2006).

    In essence, these surveys take us from an era (the 1930s) when the computational complexity of quantum chemical dynamics was perceived as EXP(n), atoms and molecules were invisibly small, and computers were unimagined, to an algorithmic era where quantum chemical dynamics is O(n^1), atomic-resolution microscopy is routine, and petaflop computations are a globalized cloud utility.

    All of these STEM capabilities (in computation, algorithms, and sensing) have been doubling every two years (or faster) for many decades. Progress in each one of these areas increases the value of the other two, and we are far from known fundamental limits to any of the three. This is good news for young researchers in pretty much all disciplines (including complexity theory, needless to say).

  229. Anonymous Says:
    Comment #229 August 16th, 2011 at 10:57 pm

    > UPDATE: Here’s an analogy. The two phrases “the President of the United States” and “Barack Obama” both pick out the same person. However, “the President in a hypothetical world where John McCain won the election” is still the President, whereas “Barack Obama in a hypothetical world where John McCain won the election” is not. Hence we’ve constructed an oracle that separates the two. 🙂

    That was an ingenious example! Relating relativization and semantics for possible worlds. So you are saying names of complexity classes are not rigid designators (in the sense of Kripke’s “naming and necessity”).

  230. Scott Says:
    Comment #230 August 16th, 2011 at 11:06 pm

    Anonymous #229:

    So you are saying names of complexity classes are not rigid designators (in the sense of Kripke’s “naming and necessity”).

    EXACTLY!

    Incidentally, I would never have thought of this example had my brain not been primed lately to look for connections between philosophy and TCS. 🙂

  231. Job Says:
    Comment #231 August 17th, 2011 at 12:58 am

    I managed to overcomplicate my question. 🙁
    Luckily, i’m also skilled at oversimplification.

    NP-Complete needle-in-haystack problems ask whether a subset of the input exists with some property.

    But it could be worse, more complex problems could ask whether a subset of the subsets has a property, or whether a subset of the subsets of the subsets has a property. That’s like asking whether a portion of the hay in the haystack can be assembled to duplicate a picasso (keeping in mind the haystack is of exponential size, and the picasso is polynomial).

    These problems seem to be in NP because they look to be polynomially verifiable (as a certificate, indicate which pieces of hay were used, where they were originally and how they were assembled), but they also look more difficult than NP-Complete problems, and should thus be outside of NP.

    I was asking whether you think these subset-of-subsets types of problems would be in NP.

  232. Anonymous Says:
    Comment #232 August 17th, 2011 at 2:15 am

    It seems so natural that now it seems strange that I haven’t thought or heard about it before. I will mention it when I talk about relativization next time I teach complexity. 🙂

  233. Sniffnoy Says:
    Comment #233 August 17th, 2011 at 3:42 am

    Hm — so what I was really wondering about with the $25.00 prize is if there’s any way that with derandomization an interactive proof could be turned into a proof in the literal sense. Because one of the things about computers is they let you do proof by computation — it’s true because I computed it. One of the things about probabilistic or quantum computation is that, while you can be very certain that the result is correct, the fact that it was output still doesn’t count as a proof. Of course if we can derandomize stuff then we can get proof-by-computation of a sort from a probabilistic algorithm (though I guess only by first converting it to a deterministic one and running that instead). So what I’m wondering is, this protocol which almost-solves the $25.00 prize, supposing that P=BPP and you can derandomize stuff… there’s no way that it would allow you to do an actual proof-by-computation with a quantum computer, would it? I guess that would require it to output a static proof along with its answer which could then be put through a proof-checker… which of course is exactly what you didn’t ask about in order to make things fair to the quantum computer. Hm.

  234. Scott Says:
    Comment #234 August 17th, 2011 at 7:47 am

    Sniffnoy #233: There are much simpler cases of interactive proofs that no one knows how to “unravel” into static proofs. For example, we don’t expect there to be a short static proof of which player has a win in chess (unless NP=PSPACE), but there is a short interactive proof because IP=PSPACE. This dramatic compression in proof length is sort of the entire point of talking about interactive proofs in the first place!

    (Well, another point is that interactive proofs can give you additional properties, such as zero-knowledge. But once again, if you could “unravel” a zero-knowledge proof into a static proof, then it would become something you could share with your friends, and would no longer be zero-knowledge at all!)

  235. Sniffnoy Says:
    Comment #235 August 17th, 2011 at 10:31 am

    Hm, I guess asking for for short static proofs is essentially the same thing as asking for BQP contained in NP, isn’t it. Or I guess actually it’s even stronger because the quantum computer has to be able to output that proof. Though I don’t know if that actually adds much difficulty. It seems as if people generally don’t expect BQP to be contained in NP, is there any particular reason for this? Do we actually have a candidate problem suspected to lie in BQP but not NP?

  236. Scott Says:
    Comment #236 August 17th, 2011 at 10:55 am

    Sniffnoy #235:

    (1) It might indeed add difficulty if the quantum computer needs to output the proof. For example, imagine an efficiently-computable function f:[N]→[N] that’s either one-to-one or else satisfies the Simon promise. If f is one-to-one, then a quantum computer can easily verify that fact (by running Simon’s algorithm). Furthermore, there’s probably an NP witness that f is one-to-one, using approximate counting (which puts the problem in AM) plus the derandomization assumptions that make AM=NP. But putting those two facts together, we still don’t get an NP witness that f is one-to-one that a quantum computer can efficiently find.

    (2) In the unrelativized world, the only good candidate we have for a decision or promise problem in BQP but not in NP is still just the tautological problem, “simulate a given quantum circuit C”!

    On the other hand, if you’re willing to consider oracle problems, then we do indeed have examples — see my BQP and the Polynomial Hierarchy paper.

    Also, if you’re willing to consider sampling or search problems, then even in the unrelativized world, we have excellent candidates for problems solvable in quantum polynomial time whose solutions are not classically verifiable. For more see my paper with Arkhipov.

  237. Sniffnoy Says:
    Comment #237 August 17th, 2011 at 11:35 am

    Well I’m certainly willing to consider search problems. 🙂 I’ll have to go actually read that now…

  238. John Sidles Says:
    Comment #238 August 17th, 2011 at 1:52 pm

    To agree with Sniffnoy (#237), we engineers are keenly interested in verifying search calculations, and hence the updated on-line version of the Aaronson-Arkhipov manuscript Computational Complexity of Linear Optics, with its expanded discussion of validation, is welcome and much appreciated.

    Even in the updated version, there still are some passages that are mighty tough (for me) to parse, in particular the assertion “We do not believe there is any NP witness for BosonSampling.”

    Apparently the notion of an “witness for sampling” (NP or otherwise) has never appeared in the literature before … in the celebrated phrase of the Nog (the Ferengi kid) on Star Trek: Deep Space 9: “What does that mean, exactly?”

    Please let me say, that the topic and the substance of Linear Optics are wonderfully interesting … so much so, as to leave readers hungry for more! 🙂

  239. Scott Says:
    Comment #239 August 17th, 2011 at 2:02 pm

    John Sidles #238: What we meant by that was a polynomial-size string w that you’d be given along with a collection of outputs s1,…,sk of a boson computer, such that using w, it’s possible to verify in classical polynomial time that s1,…,sk are “reasonable outputs” of the boson computer. (In other words, if A1,…,Ak are the n*n submatrices corresponding to s1,…,sk, then the squared permaments |Per(A1)|2,…,|Per(Ak)|2 are suitably large.) The difficulty is that, if our Permanent of Gaussians Conjecture holds, then if such witnesses existed, they would imply that P#P=BPPNP.

  240. notaphilosopher Says:
    Comment #240 August 17th, 2011 at 2:43 pm

    Scott, for a person of your level of smartness, enthusiasm, oratory etc., it may not be hard to succeed immensely outside academia as well, and that way probably you can also afford that “declared 200K” in the same way as Bill Gates does 🙂

    But I believe that will be a loss for the society and posterity in the big picture.

    I am glad to hear that you aren’t planning on doing that.

  241. A mouse Says:
    Comment #241 August 18th, 2011 at 12:00 am

    For somebody who didn’t submit because the deadline was over but didn’t see you responding to others also after the deadline until now, would you excuse a violation of your last request?

    What do people mean when they say their research is in Algorithms? Something different from Complexity Theory?

    Is there any place in the postgraduate educational system for someone who wants to take courses in lots of different mathematical/TCS specialties and is less interested in innovative research (until perhaps it arises naturally)?

  242. Scott Says:
    Comment #242 August 18th, 2011 at 12:51 am

    A mouse #241:

    What do people mean when they say their research is in Algorithms? Something different from Complexity Theory?

    Generally, “algorithms” means upper bounds, whereas “complexity theory” means lower bounds and reductions (i.e., trying to understand the fundamental limitations of algorithms). However, things get blurry around the edges: for example, an NP-completeness proof for a practical problem might get classified as “algorithms” these days, whereas a new algorithm for the unique games problem might get classified as “complexity theory.” Probably the best way to understand this is that there are two (overlapping) communities:
    – one that cares about solving actual problems faster (and is interested in complexity mostly as a barrier to that goal), and
    – one that cares about illuminating P vs. NP and the other “deep mysteries” (and is interested in algorithms mostly as barriers to that goal).

    Is there any place in the postgraduate educational system for someone who wants to take courses in lots of different mathematical/TCS specialties and is less interested in innovative research (until perhaps it arises naturally)?

    Uh, a Masters degree?

  243. Sniffnoy Says:
    Comment #243 August 18th, 2011 at 4:24 am

    Ah! I just remembered something else that was bugging me. This is probably violating several of the constraints, and is probably just something I should look up in a textbook or figure out myself, but I’m hoping you’ll be kind enough to answer it anyway now that things have cooled down. 🙂 (Although I suppose that if you continue to answer these you risk starting things up again? Hm.)

    Oracle separations. How the hell do you go from “You can’t solve [takes-an-oracle-as-input problem] faster than [complexity]” to “There exists an oracle for which [that problem, instantiated with that oracle] cannot be solved faster than [complexity]”? Like I know how to prove that comparison-based sorting can’t be done faster than nlogn, but how do you go from there to showing that there is an actual total ordering which is sufficiently hard to work with that, had you a comparison oracle for it, the fastest way to sort would indeed be to use the oracle and thus take nlogn time? From the way that people seem to typically implicitly equate the two I assume this is a general trick…

  244. Thomas Says:
    Comment #244 August 18th, 2011 at 4:27 am

    “Would you rather be the sole author of a proof that P ~= NP (or that P=NP) or be alive when an alien spaceship(s) visits earth for the first time?”

    I’d choose aliens and ask them about P vs NP.
    If they can make it to earth they probably have good insights into the question, but if they don’t then well maybe it’s not that fundamental after all..

  245. math idiot Says:
    Comment #245 August 18th, 2011 at 9:40 am

    This is the most interesting blog that I have ever read here! A lot of different questions were asked and I can know some of your thinking from your answers.

  246. Scott Says:
    Comment #246 August 18th, 2011 at 9:58 am

    Sniffnoy #243: The one-word answer to your question is diagonalization. I.e., following Baker, Gill, and Solovay in 1975 (who first used the technique in this context), you construct an oracle that encodes infinitely many problem instances (one for each value of n), such that the nth problem instance causes the nth oracle Turing machine to fail. That way, every oracle TM will fail on at least one problem instance, and you’ve achieved the separation you want.

    For more details see here or here for example.

  247. Sniffnoy Says:
    Comment #247 August 18th, 2011 at 10:43 am

    Thank you, that is probably not something I would have thought of!

  248. John Sidles Says:
    Comment #248 August 18th, 2011 at 11:04 am

    Scott asserts in #239:

    “What we meant by [’NP witness for BosonSampling‘] was a polynomial-size string w that you’d be given along with a collection of outputs s1,…,sk of a boson computer, such that using w, it’s possible to verify in classical polynomial time that [that] the n*n submatrices corresponding to s1,…,sk, then the squared permaments |Per(A1)|2,…,|Per(Ak)|2 are suitably large.”

    It seems to me, Scott, that the conjecture There is no NP witness for BosonSampling is plausible if we parse the above definition strictly literally.

    And yet, it is also true that if for the key phrase “s1,…,sk of a boson computer“ we substitute “s1,…,sk of a classical computation in P“ and we then call the resulting definition an “NP witness for simulated BosonSampling,” the article provides *no* grounds to conjecture There is no NP witness for simulated BosonSampling, that is to say, neither the manuscript itself nor the references presents an argument that (AFAICT) even attempts to exclude this possibility.

    Because supposing that Alice gives w to Bob, and Bob simulates (by some classical means) s1,…,sk, can’t we conceive that Bob — by virtue of his classical construction — can supply certificates that |Per(A1)|2,…,|Per(Ak)|2 are (in your phrase) “suitably large”? Indeed, we quantum simulationists are nowadays contemplating algorithms that are designed to achieve precisely this effect.

    Here the point is that ordinary words like “verification” and even technical phrases like “witness for sampling” can reasonably be parsed in more than one way. In particular, the main conclusion of the Linear optics manuscript, that “rudimentary quantum computers built entirely out of linear-optical elements cannot be efficiently simulated by classical computers” is sensitive to the nuances of these parsings, and therefore cannot be taken strictly at face value.

    With reference to the (wonderful!) comment #242 above, the preceding remarks reflect a point-of-view mainly originating in the “cares about solving actual problems” community, that moreover appreciates and admires the topic, the substance, and both the fundamental and practical implications of Linear Optics … and that hopes therefore for a scrupulously well-posed statement of its implications.

    And thank you also, for creating and sustaining this wonderful weblog Shtetl Optimized.

  249. Scott Says:
    Comment #249 August 18th, 2011 at 12:06 pm

    John, I think we were pretty explicit that by “simulate,” we meant sample from the same probability distribution as the experiment does (or one that’s close to it in variation distance). We mentioned the hardness of sampling from a distribution indistinguishable from the correct one by any polynomial-time algorithm as an interesting open problem.

    So your objection seems to boil down to saying that, if you ask a different question than the question we asked, it might have a different answer than the answer we gave. And I agree with that! 😀

  250. John Sidles Says:
    Comment #250 August 18th, 2011 at 12:58 pm

    And Scott, I agree with you that these technical clarifications are very sensible and useful … which is a good reason to include them in the article, not just on your weblog!

    It’s evident that once-shared terms like “efficient”, “verifiable”, and even “simulation” — to say nothing of novel terms like “sampling witness” — now are accreting complexity-theoretic technical meanings that (unless due care is taken to state these meanings explicitly) make it hard for students to read broadly in the literature, and hard also for the “actual problem” and “deep mystery” communities (of #242) to appreciate and assist one-another … as in the long run, they surely must do.

    This care is important especially for a manuscript like Linear Optics, which unlike any other complexity theory manuscript (known to me), asserts that “The most exciting challenge we leave is to do the experiments” … “the possibility of actually building a scalable linear-optics computer.” For this physical instantiation to happen, the ideas in Linear Optics manuscript will have to be read-and-understood by an exceptionally broad base of readers, many of whom will be unfamiliar with the specialized vocabulary of complexity theory, and the various subtleties that this vocabulary associates even to the ordinary terminology of physics and engineering.

    So if some of the clarifications on this thread were infused into the article — in particular the multiple plausible definitions and complexity-theoretic subtleties associated to the notion(s) of “NP witness for BosonSampling” — these clarifications would be very welcome to me, and I think to many engineers and physicists.

  251. The Gnome in the Phone Says:
    Comment #251 August 19th, 2011 at 12:00 am

    Why aren’t you donating to the East Africa fund? Why aren’t you saving the children? What you suffered isn’t remotely as horrifying as losing a child, or a whole family to fucking famine.

  252. helpneeded Says:
    Comment #252 August 19th, 2011 at 9:53 am

    Comment #16

    Regarding your comment. Isn’t it obvious that you have atleast candidates?
    1) Deciding regularity of Navier-Stokes
    2) Multi-body dynamics
    3) Classical chaos (as opposed to quantum chaos studied by Peter Sarnak)

  253. Scott Says:
    Comment #253 August 19th, 2011 at 10:15 am

    helpneeded #251: All of those systems seem like reasonable candidates, provided you ignore special relativity (after all, we’re talking about solving the halting problem in finite time). But you’d still need to prove that you can actually simulate a Turing machine with them, and moreover at an asymptotically diverging rate. (And even assuming you could do so, there would remain the further question of whether you could simulate a Turing machine robustly–i.e., whether the computation would be destroyed by the tiniest perturbation of the parameters. It seems overwhelmingly likely to me that it would be destroyed.)

  254. Scott Says:
    Comment #254 August 19th, 2011 at 2:47 pm

    The Gnome in Phone #251:

    Why aren’t you donating to the East Africa fund? Why aren’t you saving the children? What you suffered isn’t remotely as horrifying as losing a child, or a whole family to fucking famine.

    Actually, I do give to charities like VillageReach that are doing great work in Africa. No doubt I could (and should) give even more—but may I ask how much you give? It’s easy to criticize behind a cloak of anonymity.

  255. helpneeded Says:
    Comment #255 August 19th, 2011 at 10:55 pm

    Comment #16, #252 #253:
    I had a very very vague idea. Pardon me if I don’t make sense. How about considering the set of all strings whose Kolmogorov complexity is the cardinality of R or higher cardinalties? I am pretty sure the set of all strings can be assumed to have been produced in the classical world. Probably use the fact that they are dense enough to accommodate 1 string which can simulate the Turing machine. Any thing along those lines?

  256. helpneeded Says:
    Comment #256 August 19th, 2011 at 10:56 pm

    preproduced* I meant!

  257. Hopefully Anonymous Says:
    Comment #257 August 20th, 2011 at 12:44 pm

    I agree with you that President Obama was the best president since you were born, although to be fair, I think that was most true at the time he passed the stimulus, and decreasingly true as he promotes “deficit reduction” over a “second stimulus” -at some point, maybe soon, he’s on track to dip below Clinton and Bush the First if he fails to self-correct.

    I’m not going to waste time asking you about that since I’m pretty sure we agree.

    My question for you is, who would you like most as President post-Obama? It would be great if you could submit and rank multiple names (like at least three).

    I think my top 3 would be Dr. Chu (Energy Secretary), Mayor Bloomberg, and Gen. Petreus -in that order, although I’d like all three to have a higher level of intermediate administrative experience first, ideally as a big population state governor.

  258. helpneeded Says:
    Comment #258 August 20th, 2011 at 1:18 pm

    I disagree Obama was the best. He had the full house and just 1 vote short of 60 in senate. Still he passed less than 1/3 of what the stimulus should have been and the structure of the stimulus was gravely compromised and he had to make up for this with a $850B tax cut in 2010. He probably is not as strong as one would like (particularly in these times). Remember in a capitalist economy with banks serving as the heart that pumps money, stimulus is a one-time help when the heart malfunctions. Even when the heart is out of rhythm, it is better to use the heart as long as it functions.

  259. Scott Says:
    Comment #259 August 20th, 2011 at 4:23 pm

    Hopefully Anonymous #257:

    My question for you is, who would you like most as President post-Obama? It would be great if you could submit and rank multiple names (like at least three).

    I think my top 3 would be Dr. Chu (Energy Secretary), Mayor Bloomberg, and Gen. Petreus -in that order

    That’s one of the most fun questions I’ve gotten! OK, so supposing that for some strange reason I had the responsibility of unilaterally choosing a President of the United States, with a guarantee that my choice would be (at least initially) respected and accepted by the public, here are some of the candidates I would carefully interview:

    – Steven Chu (that was a fantastic choice!)
    – Steven Weinberg
    – Al Gore
    – Rush Holt (D-NJ)
    – Warren Buffett
    – Ed Lazowska (past chair of the Computing Research Association)
    – Srini Devadas (my former boss at MIT 🙂 )
    – Paul Krugman
    – Sean Carroll
    – John Preskill
    – Elizabeth Kolbert (New Yorker writer)
    – Elizabeth Warren
    – Elena Kagan
    – Al Franken
    – Jon Stewart

    I would not nominate myself—despite the fact that there are few people whose views I agree with more 🙂 —since I don’t think I have the even temperament required (or certainly not yet).

    ADDENDUM: If I also got to choose the Vice-President and the cabinet, I’d have a lot of fun deciding which of these people would be best for which position! In that case, though, I’d also want to insert some libertarian-leaning “opposition figures,” such as Robin Hanson, Steven Pinker, or Paul Graham. They’d have the opportunity to try to convince the progressive majority to try their ideas.

  260. Rhys Ulerich Says:
    Comment #260 August 20th, 2011 at 10:34 pm

    Having watched Weinberg walk out of an excellent modern ballet production because it did not jive with his preconceived classical ballet world view, I humbly ask for a more open-minded second choice in your list.

  261. Scott Says:
    Comment #261 August 20th, 2011 at 11:35 pm

    Rhys Ulerich #260: Do you have any idea who you’re dealing with here? Your anecdote sorely tempts me to move Weinberg to the top of the list! 😀

    (Though I do differ from Weinberg in that I doubt I could sit through a classical ballet production either…)

  262. Peter Sheldrick Says:
    Comment #262 August 21st, 2011 at 5:05 am

    adding to the question ‘What to do if you think you can multiply matrices in near-linear time’ or #184
    ‘Why do you think there is no elementary approach to [matrix multiplication]?’ by helpneeded

    You can test it against the special case of circulant matrices – these special matrices all get diagonalized by the DFT matrix – so the cost of diagonalizing them is the same as FFT O(nlogn). And when it’s diagonalized you are just multiplying n numbers which is conceptuatlly much easier…

    care to get in contact helpneeded? The best thing is i think if you can start a question on math stackexchange – i hang out there a bit http://math.stackexchange.com/users/11260/peter-sheldrick

  263. Hopefully Anonymous Says:
    Comment #263 August 21st, 2011 at 6:51 am

    “I would not nominate myself—despite the fact that there are few people whose views I agree with more —since I don’t think I have the even temperament required (or certainly not yet).”

    Well, if you happen to go the Dr. Chu route and turn out to be highly talented at administering large bureacracies, I do hope you consider running for Governor and then President.

  264. helpneeded Says:
    Comment #264 August 22nd, 2011 at 1:25 am

    @Peter Sheldrick Thanks for getting that comment#262 out. I have already finished the proof. It is in good hands now. If it succeeds, you will see it out in a month or so!!

  265. helpneeded Says:
    Comment #265 August 22nd, 2011 at 1:44 am

    Scott: comment#183 “Yes, it could be such evidence. For more see Section 8.1 of my philosophy paper.” I read through your paper(I mean the relevant section). I am afraid, your writing style is different and may be I am not familiar with the topic. I could only get bits and pieces. Say someone invents a superpolynomial algorithm for integer factoring that beats the current subexponential algorithm of number field sieve, would it change the philosophical outlook to QM in anyway?? I acually like your idea of polynomial time Hidden variable QM. That seems reasonable! Would factoring in superpolynomial time help address this issue??

  266. helpneeded Says:
    Comment #266 August 22nd, 2011 at 1:50 am

    Also comment#183: In your paper, you have argued against many-worlds interpretation. Does non-evidence of SUSY at LHC provide evidence of this fact?(asking this question for my knowledge).

  267. Scott Says:
    Comment #267 August 22nd, 2011 at 8:55 am

    helpneeded: If it turned out that there was a polynomial-time classical factoring algorithm, that would remove one major piece of evidence for BPP≠BQP. (There would, however, still be other evidence, especially if you were willing to consider BPP versus BQP sampling and search problems.)

    And if BPP=BQP, then in many people’s minds, that would indeed have fundamental implications for QM (since it would open up the possibility of “polynomial-time hidden variable theories,” as my article discussed). But other people would probably treat it as “just” a mathematical discovery with no physical or philosophical implications at all. Maybe it would depend on the details of how BPP=BQP was proved.

    SUSY has nothing whatsoever to do with the many-worlds interpretation. Indeed, I hate to disappoint you, but as long as quantum mechanics remains our basic framework for physics (the situation we’ve been in since 1926), it’s hard to imagine any experimental discovery that would bear on MWI. (Except, maybe, an experiment that placed conscious human beings into coherent superpositions … but such things are not on the agenda at the LHC. 😉 )

  268. helpneeded Says:
    Comment #268 August 22nd, 2011 at 1:57 pm

    http://en.wikipedia.org/wiki/Grover

    Regarding Grover’s algorithm on searching, I thought the O(\sqrt(N)) bound was ‘provably’ impossible in the classical world! Wouldn’t that be some kind of ‘proof’ for BPP!=BQP (just asking). Is the argument that this is inconclusive is because Grover’s trick is not an exponential speedup?

  269. Scott Says:
    Comment #269 August 22nd, 2011 at 2:37 pm

    helpneeded #268: Grover’s algorithm actually fails to show BPP≠BQP for two reasons. The first reason is that (as you mentioned) it’s only a polynomial rather than an exponential separation. The second reason is that the separation is at the wrong “scale”: ultimately we want n versus n2 or exp(n), rather than log(n) or √n versus n. But in the former case the separation of Grover’s algorithm is no longer a proven one. (E.g., if you use an input of size n to describe a list of size n10 in some “implicit” way, then Grover’s algorithm can search that list in only O(n5) steps, but maybe some clever classical algorithm can too!)

    And that’s enough! I’ll have another “Ask Me Anything” next summer. 🙂

  270. helpneeded Says:
    Comment #270 August 22nd, 2011 at 2:47 pm

    Interesting! Thankyou so much:)!!

  271. John Sidles Says:
    Comment #271 August 22nd, 2011 at 3:11 pm

    Thank you for this fine series, which we may hope continues for fifty years and more (and what a Festschrift that would make!).

    I had another question relating to the important-yet-opaque notion of an “NP witness for sampling”, but such witnesses have sufficiently broad application that the question matched well with today’s (also-wonderful) GLL&P=NP topic Testing Galactic Algorithms.

  272. Neel Krishnaswami Says:
    Comment #272 August 24th, 2011 at 8:56 am

    For more of a “challenge,” how about the Classification of Finite Simple Groups? 😉

    No smiley needed: I’m down the hall from George Gonthier, who is working on precisely this problem. It’s actually an excellent test problem for machine-checked proof, because it’s (a) enormous, and (b) one of the pinnacles of modern mathematics. The first point means that if you can handle it, you know you aren’t missing some critical feature needed for modular proof development, and the second point means that your proof assistant can formalize all the really wild tricks that mathematicians have thought up.

    As an aside, MIT just hired Adam Chlipala, who is another expert on using proof assistants. You might enjoy talking with him.

  273. Scott Says:
    Comment #273 August 24th, 2011 at 9:53 am

    Neel #272:

    As an aside, MIT just hired Adam Chlipala, who is another expert on using proof assistants. You might enjoy talking with him.

    I’ve already had some very enlightening conversations with him and hope to have more!

  274. Shiri Dori-Hacohen Says:
    Comment #274 September 2nd, 2011 at 4:44 pm

    Very late to the game, but just wanted to mention re: #259, even though I agree with Warren Buffett as a choice, I highly doubt that he would resign Berkshire-Hathaway to step up! He likes what he does way too much. All in all, great Q&A session!

  275. helpneeded Says:
    Comment #275 September 17th, 2011 at 3:24 am

    The MM attempt failed. I am very very surprised though!! I have not seen this approach. Not because the complexity is bad. But the one choice of parameters I could make the complexity work gave me a deficient work. It is very elementary. But I have not seen this method before in my literature search starting from 1970. I could probably have figured it out earlier if I had a fully loaded Mathematica! Would you be interested in atleast taking a look? I have a certain feeling it is a totally different approach than you most likely would have seen before!! I do not know whether to give up or not since the literature search also came out empty but the matrices involved have so much structure.

  276. helpneeded Says:
    Comment #276 September 17th, 2011 at 3:25 am

    I mean ‘gave me a rank deficient matrix’ not a ‘deficient work’.

  277. helpneeded Says:
    Comment #277 September 20th, 2011 at 12:51 am

    I thought more about it. I found why it failed. So I won the challenge:)

  278. Links « Front to Back Books Says:
    Comment #278 January 12th, 2012 at 6:18 am

    […] Aaronson’s blog on Quantum computing, Shtetl-Optimized, boarders on required reading  – Ask Me Anything is good where he answers any and all questions posed to him over a span of days – but just […]

  279. Ask me anything « knitnut.net Says:
    Comment #279 September 11th, 2012 at 8:39 am

    […] Subject-wise, anything goes. Just don’t ask me about stuff like transhumanism and its relation to quantum computing, or the hardness of simulating Newtonian physics. […]

  280. Shtetl-Optimized » Blog Archive » Ask Me Anything! Tenure Edition Says:
    Comment #280 May 6th, 2013 at 9:43 am

    […] edition of “Ask Me Anything.”  (For the previous editions, see here, here, here, and here.)  Today’s edition is partly to celebrate my new, tenured “freedom to do whatever the […]

  281. Google Buys Quantum Computer Lab | Pink Iguana Says:
    Comment #281 May 16th, 2013 at 7:35 am

    […] edition of “Ask Me Anything.”  (For the previous editions, see here, here, here, and here.)  Today’s edition is partly to celebrate my new, tenured “freedom to do whatever the hell I […]