Open thread #2
Alright, no more politics for a while. I’m sick of it.
Given the relative success of Open thread #1, I thought I’d give you the readers a second opportunity to ask about whatever’s on your minds, except politics. Quantum complexity classes and painting elephants are definitely fair game.
(Update: One question at a time, please!)
(Update: Thanks for the questions, everyone! The open thread is now closed. We’ll do this again!)
Follow
Comment #1 September 12th, 2008 at 10:13 pm
My anniversary, work, and sleep.
Comment #2 September 12th, 2008 at 10:17 pm
You’ll have to phrase that in the form of a question… 🙂
Comment #3 September 12th, 2008 at 10:17 pm
Well, you haven’t said: “One question per post”, yet. So I send mine in a batch.
1. What is your pattern while you study or do theory? Do you take a walk every 45 minutes or do you sit at your desk for hours at a stretch?
2. I feel that I need a break from mathematical thought after half an hour or 45 minutes; and tend not to think about anything during that time. But I know some professors have 2 hours long research meetings, and then have the patience for an office hour answering questions about theory courses;… How do they do it? What is the secret?
3. When you were a student how did you balance time between coursework, (possibly TA duty), and research work?? (Especially if in your coursework, you’re dealing with tough stuff you’ve never seen before and if you are given a lot of homework.)
—
V
Comment #4 September 12th, 2008 at 10:23 pm
1. I used to take walks constantly while working. I find I do it less now, but it may simply be because I’ve gotten lazier rather than better able to concentrate.
2. If you find the secret to concentrating for hours at a stretch, let me know! Seriously, the only way I’ve been able to do it is to become so engrossed in something that I don’t even know how much time has passed.
3. For the most part, I tried to put the minimum effort into courses required to do well, and to spend as much time as I could on research. But without any courses to take, I probably wouldn’t have succeeded at research, since my time would have been too unstructured. (Even today, I find I’m happier when I’m teaching than when I’m not.)
Comment #5 September 12th, 2008 at 10:25 pm
What texts (possibly online, but specifically “books” or survey articles rather than original research articles) do you recommend for a graduate student trying to get up to speed with the forefront of complexity?
Comment #6 September 12th, 2008 at 10:25 pm
What is on my mind is the question “What is quantum mechanics really about?”
… and I am hoping for an answer that is in the form of a narrative, nor a mathematical formalism or a physical theory.
Obviously, any formalism or physical theory that has an invariance can support more than one narrative … and quantum mechanics being loaded with invariances, it definitely supports many narratives.
Thus recognizing that there is more than one good narrative about quantum mechanics … and that it is probably best if everyone does *not* embrace the same narrative … my question therefore is the meta-question … “What are the six best answers to the question: ‘What is quantum mechanics really about?'”
Hopefully, these answers will be far more interesting in aggregate than they are individually. 🙂
Comment #7 September 12th, 2008 at 10:28 pm
AR: Computational Complexity by Papadimitriou
Complexity Theory: A Modern Approach by Arora and Barak (draft is free online)
Gems of Theoretical Computer Science by Schöning and Pruim
Course notes from Luca Trevisan
Those should be enough to keep you quiet for a while…
Comment #8 September 12th, 2008 at 10:32 pm
Did you sit through every graduate theory course offered in your department?
Comment #9 September 12th, 2008 at 10:32 pm
What are the six best answers to the question: ‘What is quantum mechanics really about?’
1. Information
2. Minus signs
3. Exponentiality
4. The L2 norm
5. Ourselves, the observers
6. All the choices in life we could have made but didn’t
Comment #10 September 12th, 2008 at 10:33 pm
Did you sit through every graduate theory course offered in your department?
Nope.
Comment #11 September 12th, 2008 at 10:35 pm
When reading texts, did you feel the need to solve the exercises?
Did you often read texts cover to cover or did you mine it only for the knowledge / techniques you were seeking?
—
V
Comment #12 September 12th, 2008 at 10:40 pm
When reading texts, did you feel the need to solve the exercises?
No, although I probably should have.
Did you often read texts cover to cover or did you mine it only for the knowledge / techniques you were seeking?
Definitely the latter. A math book is not a novel, and to read it like one is generally pure torture.
Comment #13 September 12th, 2008 at 10:43 pm
In your experience, did you find your fellow theory students somewhat distant and rather hard to befriend?
Comment #14 September 12th, 2008 at 10:46 pm
During your studies, did you feel the need to make a handy cheat-sheet to make note the important results and the web of ideas? (Or was this limited to the COmplexity zoo?)
Comment #15 September 12th, 2008 at 10:56 pm
No and no. And that’s enough from you—I mean, dude. 🙂
Comment #16 September 12th, 2008 at 11:02 pm
Well, I suppose that is enough wisdom for one night! Thanks anyway.
—
V
Comment #17 September 12th, 2008 at 11:03 pm
How do you find research problems to work on? (This is a general question, nothing to do with your specific research area.)
Comment #18 September 12th, 2008 at 11:09 pm
Lucas: In my case, at least half the time it’s been through going to conferences and talks, hearing someone say something, and thinking, “that can’t possibly be right—I’m going to take five minutes right now and disprove it!” Or maybe, “that ought to be completely trivial to prove!” And then, a month or two later, being able to prove something (though often not what I’d originally hoped).
Other times I’ll simply pick a question off my back burner, from the several dozen cached there (especially if I learn something that seems like a new angle of attack).
Comment #19 September 12th, 2008 at 11:23 pm
Scott, it looks like you somehow linked to another comment; this page appears to have a link to what you drescribed as Complexity Theory: A Modern Approach by Arora and Barak.
I’ll assume you mean one question (at a time) per questioner? (Don’t answer, thats not my question.)
I read about MIT receiving a grant for a “new graduate training program, called Interdisciplinary Quantum Information Science and Engineering (iQuISE)“, and you once suggested to me that professors were generally too busy to approach directly, and to talk to grad students to learn about specific programs. This happens to be exactly what I am interested in, but as a graduate with only a marginally relevant undergrad degree, I suspect I am not qualified (will not qualify) for acceptance into such a program.
At the moment I am attending Peter Shor’s 18.435, though I am not matriculated and only time will tell how successful I will be in the class.
My question is do you have any advice about what I can do to increase my likelihood for being accepted into the iQuISE program (assuming the program would even be open to incoming graduate students). I was thinking of emailing Isaac Chuang about it (I suppose because he is attached to the press release), and I will probably discuss it with Peter Shor at some point this semester too.
Comment #20 September 12th, 2008 at 11:23 pm
I’m a CS grad student at Waterloo. Were there any courses/activities/professors at Waterloo that you liked particularly and would recommend to others?
Comment #21 September 12th, 2008 at 11:30 pm
What theoretical evidence is there that quantum computers can’t provide an exponential speedup for solving any NP-complete problems?
I know some people who strongly believe that we will figure out a way to factor numbers in polynomial time. Do you think they are wrong? If so, why?
Please provide answers that someone who doesn’t really know much complexity theory can understand. I have only taken an undergraduate theory course and I am just starting graduate school in computer science and I have a non-theory research focus.
Comment #22 September 12th, 2008 at 11:49 pm
How do you generally organise your research work, that is: What’s your workflow, how do you start on new topics, how do you find papers to read, how do you organise them, how do you keep those “back-of-the-envelope calculations” that later might become important etc.?
Comment #23 September 13th, 2008 at 12:04 am
What is the relationship (if any) between phase transitions in physics and the ones people talk about in SAT?
Comment #24 September 13th, 2008 at 12:21 am
Any of the following:
What kind of music do you like?
Do you find the relations between math (or computer science) and music interesting?
Assuming you’ve read Godel Escher Bach, what did you think of Hofstadter’s notion that Bach’s music was strongly rooted in the type of self reference we see often in cs? Would you say any of this can or should apply to so called “mathematical music” that’s become popular among certain composers today?
Comment #25 September 13th, 2008 at 1:10 am
Seriously, the only way I’ve been able to do it is to become so engrossed in something that I don’t even know how much time has passed.
When this happens do you lose self awareness?
Comment #26 September 13th, 2008 at 3:12 am
I know this question is ill-posed: can humans solve the Hating Problem? Or can we just solve sub-cases, and so are we just an complex algorithm which generates new algorithms which (…. ) algorithm?
Comment #27 September 13th, 2008 at 3:36 am
I know you really don’t think P=NP, but if P=NP, what type of algorithm will succeed in polynomial time and what will the degree of that polynomial be?
If P=NP, will quantum computers solve anything more efficiently than regular computers?
Does P=parity P imply P=NP or would it just lead to solving Graph Isomorphism and integer factorization in P?
Any chance of holographic algorithms proving P=parity P or even P=#P?
Comment #28 September 13th, 2008 at 3:57 am
Cody:
My question is do you have any advice about what I can do to increase my likelihood for being accepted into the iQuISE program (assuming the program would even be open to incoming graduate students).
I’m involved in iQuISE too. It’s hard to give advice without knowing more about your situation—you didn’t even say what your major is. In general, research experience (whether or not directly related to quantum information) is always a plus. If you want to discuss in person, come to the weekly quantum information seminar / quantum group meeting on Mondays.
Comment #29 September 13th, 2008 at 4:12 am
Were there any courses/activities/professors at Waterloo that you liked particularly and would recommend to others?
Keep in mind that I was a postdoc there and not a student! I didn’t take courses. But I did know lots of interesting professors, including (off the top of my head) John Watrous, Richard Cleve, Debbie Leung, Ashwin Nayak, Joe Emerson, Ray Laflamme, Shai Ben-David…
I also took salsa lessons at the Flying Dog.
Comment #30 September 13th, 2008 at 4:18 am
Hi Scott,
You are now a(n Assistant) Professor at MIT. What qualities of MIT students impress you the most?
Comment #31 September 13th, 2008 at 4:19 am
You’ve addressed the following in some way before, but either you didn’t answer the question I’m asking or I don’t remember the answer. So:
What is the best argument for doing research on computation with oracles? You have said something along the lines of the most (or only) interesting questions in mathematics are those that can be expressed in terms of the halting of Turing machines. Let’s call these questions “Simple”. To my ignorant eyes, saying Simple question are the most interesting ones is inconsistent with doing research on oracles.
In particular, can you also compare using oracles to the following ways of expanding mathematics beyond the “real”?
1. The complex numbers. These have been very useful in solving Simple questions, but really they are perfectly concrete mathematical constructions — they just don’t jibe with our intuitions of what the word “number” connotes. So any objection to them is psychological. If we called them “angular magnitudes” no engineers would bat an eye.
2. The axiom of choice (AC). It is mostly useful in solving non-Simple questions. (E.g., does every vector space have a basis?) It has been psychologically useful in solving Simple questions in that it lets the solver ignore certain complications. In my experience these complications are complications because of the background of the solver, not because of the mathematics itself, and (I believe) that solutions to Simple questions using the axiom of choice can usually be re-expressed without the AC. So I would say that objections to the AC are legitimate, but often besides the point because (i) the AC isn’t really necessary to solve Simple questions, and (ii) if you care about non-Simple questions, the answer often depends on whether the AC is true.
Thanks.
Comment #32 September 13th, 2008 at 4:25 am
George said: I know some people who strongly believe that we will figure out a way to factor numbers in polynomial time. Do you think they are wrong? If so, why?
Is Peter Shor’s algorithm an algorithm that factors numbers in polynomical time? Can someone (not only Scott)answer my question?
Comment #33 September 13th, 2008 at 4:33 am
George:
What theoretical evidence is there that quantum computers can’t provide an exponential speedup for solving any NP-complete problems?
See my many posts about this under the category “Speaking Truth to Parallelism,” or the Democritus lectures, or my Scientific American article.
Briefly, we know that in the black-box setting quantum computers only give you the quadratic Grover speedup. Thus, any proof of NP⊆BQP will have to be non-relativizing (and indeed non-algebrizing—a consequence of Razborov’s quantum lower bound on the communication complexity of Disjointness). The fundamental reason for this is the linearity of quantum mechanics, which prevents the single branch of a superposition that happened to find the needle in the haystack to “shout above the rest” (i.e., get amplified to non-negligible probability within a polynomial number of steps). Thus, if there were a quantum algorithm for NP-complete problems, it would have to exploit the problems’ structure in some way beyond anything we can currently imagine, just as a classical algorithm for these problems would have to.
So, if you’re willing to conjecture P≠NP, then you might also conjecture NP⊄BQP for essentially the same reasons.
Strengthening the case, to my mind, are the known limitations of the quantum adiabatic algorithm (basically a quantum analogue of simulated annealing), which is the one quantum algorithm for NP-complete problems we know that actually does try to exploit structure. We know of some instances where classical simulated annealing gets stuck at a local optimum, while the adiabatic algorithm “tunnels through” to reach the global optimum efficiently. But we know of other instances where simulated annealing and the adiabatic algorithm both get stuck at local optima, and take exponential time to get unstuck and find the global optimum.
Obviously, nothing I’ve said rules out some amazing quantum algorithm that would be unlike anything we’ve seen. That’s why we’re dealing with conjectures, not theorems.
I know some people who strongly believe that we will figure out a way to factor numbers in polynomial time. Do you think they are wrong? If so, why?
I assume you mean classical polynomial time (we already know how to factor in quantum polynomial time).
Certainly, we don’t believe factoring is not in P with anything like the strength of conviction with which we believe P≠NP. But I’ve also heard people conjecture that factoring should be in P, and I’ve never understood what the affirmative case for that is.
Here’s how I think about it: we do know highly nontrivial polynomial-time algorithms, for instance for linear programming and primality testing. But these solve problems that we already knew how to solve efficiently in practice, long before they were formally proved to be in P. By contrast, factoring genuinely seems to be hard in practice and not just in theory.
(One corollary of this empirical perspective: I’m not willing to bet against a polynomial-time algorithm for graph isomorphism, as I’m willing to bet an algorithm for factoring. Like linear programming and primality testing, graph isomorphism seems to be quite easy in practice, at least most of the time.)
In the end, my belief in NP⊄BQP and in Factoring∉P essentially boil down to my belief in what you might call the “Law of Minimization of Miracles.”
Comment #34 September 13th, 2008 at 4:39 am
Clemens:
How do you generally organise your research work
I don’t.
Seriously, I have no philosophy on this topic, certainly none worthy of study or emulation by others. I work on whatever I can motivate myself to, for as long as I can stay motivated by it. One consequence is that I have a stack of papers that should’ve been written up years ago but that might not get written up for years more.
Recently I’ve experimented with stickK.com, with moderate success.
Comment #35 September 13th, 2008 at 4:47 am
Scott M.:
What is the relationship (if any) between phase transitions in physics and the ones people talk about in SAT?
Numerous papers have been written about this exact question, but in a few sentences: the statistical physicists have long known of situations where as you add more and more constraints to a system, it undergoes a phase change, say from numerous “unordered” solutions to a much smaller number of “ordered” solutions. (The standard example is the freezing of water into ice.) With random k-SAT, you see the same qualitative phenomenon, just in combinatorics rather than in physics. The analogy goes very deep, so much so that statistical physicists, using heuristic methods developed for physics problems, have again and again been able to (correctly) conjecture detailed properties of the k-SAT phase transition long before mathematicians and computer scientists were able to prove the conjectures.
Comment #36 September 13th, 2008 at 5:19 am
D:
What kind of music do you like?
Classic rock, jazz, blues, classical. But to be honest, music has never been a central part of my life—it’s something I enjoy but don’t go out of my way to find. I don’t have an iPod, and if I did I probably wouldn’t use it.
Everyone else in my family is extremely musical, which makes this gap in myself all the stranger. But there it is.
Do you find the relations between math (or computer science) and music interesting?
All my life, I’ve gotten variants of: “how can you possibly not be into music? Everyone who’s into math is into music! In fact, music is just math!” (I’ve heard the same about pool.) I can only reply that there seem to me to be salient differences—among them that one is based on explicit assertions that can be evaluated as true or false and the other isn’t.
On the other hand, to the extent some musical phenomenon can actually be understood mathematically, I’m as interested as the next person. John Baez, for example, has written some extremely interesting stuff about Pythagorean tuning and its connection to irrational numbers.
English prose, PowerPoint presentations, and fruit smoothies are the only media (other than math) in which I’ve even tried to create things that could rise to the level of art.
Assuming you’ve read Godel Escher Bach, what did you think of Hofstadter’s notion that Bach’s music was strongly rooted in the type of self reference we see often in cs? Would you say any of this can or should apply to so called “mathematical music” that’s become popular among certain composers today?
Sorry, no strong opinions here. If you like math and you like Bach, then it’s not surprising that you could find connections galore between them. (I’m sure there’s more mathematical structure to be found than in, for example, the works of Spears or Aguilera.) Maybe there’s more to it than that; I’m not sure.
Comment #37 September 13th, 2008 at 5:21 am
Captain Segfault:
When this happens do you lose self awareness?
Only in the ordinary sense that I’m engrossed in what I’m doing, not in some weird Zen sense.
Comment #38 September 13th, 2008 at 5:26 am
Ciro:
I know this question is ill-posed: can humans solve the Hating Problem?
Alas, the problem of hating has been with us since the beginning, and will no doubt be with us until the Singularity if not longer. 🙂
Comment #39 September 13th, 2008 at 5:36 am
Anonymous Programmer:
I know you really don’t think P=NP, but if P=NP, what type of algorithm will succeed in polynomial time and what will the degree of that polynomial be?
For obvious reasons, I have not the faintest clue what such an algorithm would look like. However, I’ll stick my neck out and conjecture that, if there were a polynomial-time algorithm for 3SAT, then there would probably also be one with a “reasonable” running time (say, no more than n8).
If P=NP, will quantum computers solve anything more efficiently than regular computers?
That’s a great question! Formally, we don’t know: even assuming P=NP, we don’t know how to simulate quantum systems in classical polynomial time. All we know is that P=P#P implies P=BQP; we don’t know if P=NP implies it. (This is yet another reason to be interested in the old open problem of whether BQP is in the polynomial hierarchy: if it is, then P=NP would imply P=BQP.)
In practice, though, all the cryptographic problems you might want to use a quantum computer for (such as factoring and discrete log) would be solvable in classical polynomial time if P=NP.
Does P=parity P imply P=NP or would it just lead to solving Graph Isomorphism and integer factorization in P?
Another good question! Valiant-Vazirani proved that NP ⊆ RP⊕P. So if P=⊕P, then NP=RP, which is “almost as good” as P=NP (and indeed, implies P=NP under a standard derandomization hypothesis).
Any chance of holographic algorithms proving P=parity P or even P=#P?
Obviously there’s a chance, but personally I’ve never regarded this possibility as a particularly serious one. (We could list 500 other things that have a “chance” of proving P=P#P…)
Comment #40 September 13th, 2008 at 5:45 am
What qualities of MIT students impress you the most?
There’s a wide range of students, just like anywhere else. But there are students here who’ve impressed me with all the things you’d expect (creativity, brilliance, perseverance…)
Comment #41 September 13th, 2008 at 5:46 am
Is Peter Shor’s algorithm an algorithm that factors numbers in polynomical time?
Yes, in quantum polynomial time.
Comment #42 September 13th, 2008 at 6:49 am
According to the time hierarchy theorem there are problems in the arbitrary high exponent parts of P. Isn’t that kind of contradictory to the textbook justification of the practical relevance of P vs NP that problems once recognized to be in P often turn out to need only low exponents? Maybe the latter is more of an empirical observation. But doesn’t this state of affairs indicate that the high exponent parts of P aren’t as well understood? Why shouldn’t a polynomial time SAT algorithm in P (if there is one) come with an absurdly high exponent?
Comment #43 September 13th, 2008 at 7:35 am
I’d like to think that having a quantum computer around to analyze the data from the LHC would greatly increase our chances of detecting SUSY. And I’d also like to think that this thought would put a smile on Scott’s face…;^)
Comment #44 September 13th, 2008 at 7:39 am
What , in your opinion, are the best arguments a pseudorandomness researcher could present to show the importance of his/her field of study ?
Comment #45 September 13th, 2008 at 7:45 am
Note: I am a grad student looking for a field, that’s why I asked the previous question.
Comment #46 September 13th, 2008 at 8:43 am
Scott,
“…I’ll stick my neck out and conjecture that, if there were a polynomial-time algorithm for 3SAT, then there would probably also be one with a “reasonable” running time (say, no more than n^8).”
Maybe it’s a bit unfair to ask… but I’m actually really curious why your intuition tells you this? It feels about right to me. But this is probably for aesthetic reasons, and I’m not a complexity theory expert.
Comment #47 September 13th, 2008 at 9:13 am
Q. There’s a goldmine of work towards approaching complexity classes and the fundamental limitations of computing power in both classical and quantum regimes. To take a wild leap into the unknown – how many established theoretical computer scientists have actively considered the possibilities of computatation based on alternative physics models? For example, I’m familiar with quantum computing in the presence of closed timelike curves, but am curious if computing at the Planck scale, quantum gravity computers (too early to say), or even moreso – the implications of higher dimensional string theory models could pose new capabilities in the future. I know it’s too early to say anything concrete as these fields are still in their early stages, but I’m thinking in context of thought experiments. Any pointers would be appreciated.
Comment #48 September 13th, 2008 at 9:52 am
roland: You answered your own question. Yes, obviously it’s just an empirical observation; in principle the exponent could be arbitrarily high.
KaoriBlue: I also made that “n8” guess primarily for aesthetic reasons. Keep in mind that in math and science, aesthetics isn’t just for its own sake; it’s one of the best guides for making accurate predictions.
Also, since P≠NP, my prediction is permanently safe. 🙂
Comment #49 September 13th, 2008 at 9:54 am
Cynthia: It’s actually not clear at all to me how a quantum computer would help in analyzing LHC data, except that maybe you could use Grover’s algorithm to search for interesting events.
Comment #50 September 13th, 2008 at 9:58 am
What , in your opinion, are the best arguments a pseudorandomness researcher could present to show the importance of his/her field of study ?
Sumwan: I’d think the best arguments would be
(1) the spectacular successes of the derandomization program within just the past decade (e.g., the AKS algorithm and L=SL)—this is clearly a vibrant field, and
(2) the close connection that we now know (e.g., from Impagliazzo-Kabanets) between derandomization and circuit lower bounds—suggesting that derandomization might be a “necessary warmup” to the P vs. NP question.
Comment #51 September 13th, 2008 at 10:00 am
Higgs Boson: See my survey article NP-complete Problems and Physical Reality—it’s all about this.
Comment #52 September 13th, 2008 at 10:17 am
Higgs Boson asks: “How many established theoretical computer scientists have actively considered the possibilities of computation based on alternative physics models?”
To answer your question with a “spin”, pretty much every simulation researcher (both classical and quantum) takes a passionate interest in the computational aspects of alternative physics models.
The reason is simple. From an informatic point of view, the goal of simulation research is to find a low-dimension, computationally efficient models that accurately simulate the behavior of high-dimension, computationally inefficient models.
If this means introducing “alternative physics”, for example in the form of low-dimension curved state-spaces instead of high-dimension linear state-spaces … well … so be it!
In fact, the idea of simulating conventional physic models via unconventional physics models is one of the most popular of all simulation strategies … the idea being to encode complicated system dynamics implicitly into state-space geometry, with consequent gains in computational efficiency.
Adopting this point of view induces the (very pleasant IMHO) feeling that the ordinary physics of ordinary everyday reality has a far richer quantum informatic structure, and consequently presents many more opportunities for fundamental research and creative enterprise, than is commonly taught in introductory courses and textbooks.
There is an article by Ashtekar and Schilling (arXiv:gr-qc/9706069) that is quite fun to read from the point of view that even if the “true” quantum mechanics of Nature is linear, the geometry of nonlinear quantum mechanics still has immense practical utility.
Comment #53 September 13th, 2008 at 11:14 am
Is there some quantum computer simulation program on web or to bay or at universities etc or somthing, which can simulate on my desktop computer the quantum computer? For example I have another program which generating prime big number in n^2 or n^3 time and I giving this generated large say 20-100 or maybe more bits or decimal digits prime number and I want, that quantum computer simulated on my computer would factorize it. I nothing know about how this simulators programs working in C++ or in Pascal, I don’t matter, I just want (or have) to generate some random big prime number of say 50 bits lenght and want to feed this number to simulated quantum computer in program and want just after writing this number (not so long task/job, anyway) into quantum computer simulation program to get instantly or to wait some a hour and to get answer of factorized number. So I guess, this would take some 2^n time, for simulation so there probably will be possible to factorize much smaller number than with classical algorithm, but I want to know is somebody written such simulation program of Shor’s algorithm?
Also I would want to know if exist simulation of quantum computer with grover’s algorithm and I would like to feed some problems into it and to see, how long for it would take to calculate (of course exponentionaly), but I want to know is such program exist?
Just a though: maybe writing such program is NP complete task or somthing?
Comment #54 September 13th, 2008 at 11:16 am
1) Are there any results known in the direction of Arthur -Merlin games, class AM[f(n)], when f(n) is a sublinear slow growing function, say polylog(n) ?
2) I am an undergrad student (Btech in Computer Science) interested in the iQuISE program, how can I proceed ?
Comment #55 September 13th, 2008 at 11:39 am
In the interview here Donald Knuth expresses his distaste with the current trend toward multi-core architectures. How do you feel about it?
Comment #56 September 13th, 2008 at 11:46 am
To Scott and anyone who is in a position of academic authority:
What do you consider the most when you reviwe a postdoc application:
– The number and quality of publications?
– The overall resume of the applicant (career history, well roundedness, other talents besides research, etc…)?
– Research plan and correspondance with desired research profile?
– Connections and fame of PhD supervisor?
– None of the above?
Having just gotten my 10^n th postdoc application rejection, I can’t help but ask.
Comment #57 September 13th, 2008 at 11:58 am
the spectacular successes of the derandomization program within just the past decade (e.g., the AKS algorithm and L=SL)—this is clearly a vibrant field
Is the AKS algorithm an example? It’s evidence that derandomization is true, but does it have to do with the derandomization program? L=SL definitely sounds connected to Sumwan’s question of pseudorandomness.
Comment #58 September 13th, 2008 at 12:24 pm
Is there some quantum computer simulation program on web or to bay or at universities etc or somthing, which can simulate on my desktop computer the quantum computer?
Yes. Try typing quantum computer simulator into Google. You’ll find numerous options, all of which unfortunately entail an exponential slowdown compared to the real thing. Or you could write such a simulator yourself (it’s not hard).
Comment #59 September 13th, 2008 at 12:34 pm
gopala:
1) Are there any results known in the direction of Arthur -Merlin games, class AM[f(n)], when f(n) is a sublinear slow growing function, say polylog(n) ?
Wait … are you talking about f(n) time or f(n) rounds of interaction?
If the former: I don’t know of any results directly about that (which doesn’t mean there aren’t any). However, any results about relativized AM, or AM in the presence of an oracle, will be applicable to that setting if you just “scale them down by an exponential.”
If the latter: see here for a start.
2) I am an undergrad student (Btech in Computer Science) interested in the iQuISE program, how can I proceed ?
There will be a website up soon with application info.
Comment #60 September 13th, 2008 at 12:42 pm
Donald Knuth expresses his distaste with the current trend toward multi-core architectures. How do you feel about it?
I doubt the chip designers have that much choice in the matter. Moore’s Law is not a law; we knew from the beginning that it had to end at some point, with all further improvements coming from parallelization (or conceivably quantumness). If we haven’t reached the endpoint of miniaturization quite yet, we’ll get there soon enough.
Comment #61 September 13th, 2008 at 12:44 pm
What do you consider the most when you reviwe a postdoc application
Quality of results and recommendation letters.
Comment #62 September 13th, 2008 at 12:46 pm
Is the AKS algorithm an example? It’s evidence that derandomization is true, but does it have to do with the derandomization program?
Yes! Recall how the AKS algorithm works: by formulating primality testing as a special case of the Polynomial Identity Testing problem, then derandomizing that special case. This fits in beautifully with the derandomization program.
Comment #63 September 13th, 2008 at 12:54 pm
CS: When this happens do you lose self awareness?
S: Only in the ordinary sense that I’m engrossed in what I’m doing, not in some weird Zen sense.
How are they different?
Comment #64 September 13th, 2008 at 12:57 pm
How are they different?
Ommmmmmmm.
Comment #65 September 13th, 2008 at 1:06 pm
What is your opinion on the 3n+1 problem’s decidability?
Comment #66 September 13th, 2008 at 1:07 pm
I meant the actual “loss of self-awareness” part, not the means to the end part?
Comment #67 September 13th, 2008 at 1:13 pm
Brenton: My guess would be that it’s decidable, and the problem is just that (as Erdös put it) “mathematics is not yet ready” to find the proof. Then again, I’d make the same guess for pretty much every other open problem in number theory that doesn’t explicitly encode a Gödel sentence.
(Note also that, if the 3n+1 conjecture was proven undecidable, then we’d know it was true. For any counterexample could be checked by computer. But of course it’s logically consistent for certain problems in number theory to be undecidable, without our being able to prove it … or to prove that their undecidability is undecidable, etc.)
Comment #68 September 13th, 2008 at 1:15 pm
KJ: Sorry, this line of questioning is getting too metaphysical.
Comment #69 September 13th, 2008 at 1:47 pm
Scott, have you seen Charles Petzold’s new book, The Annotated Turing? It’s basically an annotated version of Turing’s 1936 paper, but with lots of side-trips to give historical background and explain the philosophical ramifications of the ideas presented. It can be a little bit tedious when he’s plowing through the mechanics of how a Turing machine works, but overall the writing is very engrossing. I think it would be a great book for, say, a talented high-school student who has an interest in computers and would like to learn more about what TCS is all about.
Anyway, I guess I don’t really have a question for you, just wanted to give a shout-out for the book.
Comment #70 September 13th, 2008 at 1:48 pm
Kurt: No, I haven’t seen it. Sounds interesting!
Comment #71 September 13th, 2008 at 2:00 pm
I was referring to the f(n) rounds of interaction and i got what I was looking for. But ended up getting more food for thought! However presumably, don’t we assume synchrony when we talk of interaction in AM games ? If this so, don’t these two measures yield similar results (probably displaced by a factor) ?
Comment #72 September 13th, 2008 at 2:07 pm
If this so, don’t these two measures yield similar results (probably displaced by a factor) ?
No. AMTIME(polylog n) is a severely restricted class, which doesn’t even contain all of P.
Comment #73 September 13th, 2008 at 2:22 pm
Here’s a slightly strange question:
Do you ever run simulations or otherwise use a classical computer to aid your thinking/intuition about a problem? If I gave you a BlueGene system, paid the power bills, and prevented you from selling it off piece by piece to pay for additional graduate students and whiteboards… is there anything in particular you’d use it for?
I’m not talking about looking up papers and searching on google! 🙂
Comment #74 September 13th, 2008 at 2:30 pm
Scott, can you comment something on how the possible outcomes of the LHC on 21st October, can have effect on your research? I know it’s too general but I cannot ask more specific since I am not an expert but am curious if you are thinking seriously about the outcomes.
Comment #75 September 13th, 2008 at 2:35 pm
Never mind my question Scott. You already answered it.
Comment #76 September 13th, 2008 at 2:47 pm
KaoriBlue:
Do you ever run simulations or otherwise use a classical computer to aid your thinking/intuition about a problem?
Absolutely! You kidding? I used to do this constantly—less so now, but still at least once a month or so.
I’m not quite sure what I’d use a BlueGene for, but I’m sure I’d think of something. (Last year my summer student Eyal Dechter did a project involving MATLAB simulations of a quantum-state reconstruction algorithm, in which computation time really was a limiting factor…)
Comment #77 September 13th, 2008 at 2:48 pm
Nagesh: I can’t think of any outcome of the LHC that would have any effect whatsoever on my research … unless it starts spitting out NP oracles or something.
Comment #78 September 13th, 2008 at 2:54 pm
Note also that, if the 3n+1 conjecture was proven undecidable, then we’d know it was true. For any counterexample could be checked by computer.
Actually that’s not true. There could be an infinite orbit.
Conway proved that there exist 3n+1-style problems that are in fact undecidable. I have not seen the argument, but I suspect that he found some form of Turing universality in sequences of this type. I also don’t know what counts as a problem in the same style. I am fairly sure that the only allowed dynamic is a mapping of congruences, but I do not know what decision criterion Conway used, whether it was the existence of an infinite orbit or something else.
Comment #79 September 13th, 2008 at 3:04 pm
Greg: Duhhh, you’re right of course—the original 3x+1 conjecture is a Π2 statement. To get a Π1 statement, we’d need to consider the variant that says “the only cycle is {1,2,4}.”
Comment #80 September 13th, 2008 at 3:17 pm
derandomizing that special case
I don’t buy it; you could say similar things about Miller’s algorithm, which predates the derandomization program. Similarly, the lack of citations to anything that looks to me like derandomization suggests that they weren’t inspired by its techniques.
Can you point to any discussion that elaborates on the view of AKS as derandomization?
Comment #81 September 13th, 2008 at 3:24 pm
Perhaps its a bit late in this thread for an entirely new question, but here goes: Which of your strongly-held beliefs do you think is mostly likely to be widely perceived as ridiculous and/or proven false 50 years from now?
Comment #82 September 13th, 2008 at 3:40 pm
Greg@78:
See http://en.wikipedia.org/wiki/FRACTRAN . Any Turing machine can be simulated by FRACTRAN
running on some set of fractions. The trick is to factorise the state p into primes and think of
the exponent of the nth prime as the contents of register number n .
Comment #83 September 13th, 2008 at 3:57 pm
Besides, algorithmic theory, which subfields of computer science do you find most interesting?
Comment #84 September 13th, 2008 at 4:07 pm
Only in the ordinary sense that I’m engrossed in what I’m doing, not in some weird Zen sense.
I go the other way — the “weird Zen sense” is not weird at all, but exactly the same ordinary thing, assuming, like me, that you do not attach any religious/metaphysical significance to it.
With that said, I suspect that this is less ordinary than you think. I asked around a while back and rather surprisingly found that many/most(?) people I asked do not experience it. (how unfortunate!)
Comment #85 September 13th, 2008 at 4:10 pm
Douglas: Agrawal is a hard-core complexity theorist, and was explicitly motivated by the connection to polynomial identity testing—I don’t know how it could possibly get more clear-cut than that. See here for a paper of his that elaborates on this viewpoint.
Comment #86 September 13th, 2008 at 4:12 pm
Scott:
On the other hand, to the extent some musical phenomenon can actually be understood mathematically, I’m as interested as the next person. John Baez, for example, has written some extremely interesting stuff about Pythagorean tuning and its connection to irrational numbers.
Never mind that; Baez has also written on the use of technical mathematical apparatus (particularly group theory and combinatorics), which has become standard among today’s music theorists. See here (and, for more, here and here).
But I’ve also heard people conjecture that factoring should be in P, and I’ve never understood what the affirmative case for that is.
Shor’s algorithm + Church-Turing thesis?
Comment #87 September 13th, 2008 at 4:12 pm
Mark:
Which of your strongly-held beliefs do you think is mostly likely to be widely perceived as ridiculous and/or proven false 50 years from now?
My belief that … no, no, wait, I just stopped holding it before I could finish the sentence.
Comment #88 September 13th, 2008 at 4:15 pm
Besides, algorithmic theory, which subfields of computer science do you find most interesting?
AI, computational biology, applied computer security…
Comment #89 September 13th, 2008 at 4:18 pm
Shor’s algorithm + Church-Turing thesis?
That argument has no bite for me. If anything, Shor’s algorithm makes me less likely to think factoring is in P, since it strengthens my belief that where factoring algorithms exist someone would have discovered them by now.
Comment #90 September 13th, 2008 at 4:37 pm
Is this true that one suggestion for solving NP-complete problems is to have the Theory of Everything in hand? And do you think humans will ever find the theory of everything? (By means of a theory which describes every phenomenon in the nature and nobody will ever find anything out of its scope?)
Comment #91 September 13th, 2008 at 4:45 pm
Sina, I have no idea whether humans will find a Theory of Everything—and even if we do find it, whether we’ll know we’ve found it. But even supposing we had such a theory, currently we have no good reason to believe it would let us solve NP-complete problems in polynomial time.
Comment #92 September 13th, 2008 at 5:03 pm
Might there exist real halting or NP oracles in the wilderness? Perhaps logicians should literally go on safari to find and capture them?
Comment #93 September 13th, 2008 at 5:15 pm
Might there exist real halting or NP oracles in the wilderness?
What kind of answer were you expecting? 🙂 Yes, of course there might exist halting or NP oracles, just like there might exist perpetual-motion machines or polka-dotted dragons. The only question we could be in a position to answer is, what do our best current theories say is likely?
Comment #94 September 13th, 2008 at 5:31 pm
Well, I was just thinking that instead of trying to restrict access to oracles and so forth, maybe we should actually try finding them? As you said: they’re subtle but not malicious. I bet they won’t hide if we look for them! Where exactly, I’m not sure.
Comment #95 September 13th, 2008 at 5:50 pm
Thanks for the response Scott. Currently (even though I am not a citizen) I care a lot that Obama should win so can I ask you why you are sick of politics. I know you told not to ask about politics but I hope to know why you don’t care or want to think about it now.
I hope I am not violating the rules of the thread very seriously 🙂
Comment #96 September 13th, 2008 at 5:57 pm
maybe we should actually try finding them? … Where exactly, I’m not sure.
That would be my question as well.
Comment #97 September 13th, 2008 at 6:08 pm
Scott,
I don’t think my question was as self-contradictory as you seem to think. You can hold a belief now, and still state that (choosing from among your various beliefs) it is more likely than alternative beliefs to be proven false.
Comment #98 September 13th, 2008 at 6:13 pm
Nagesh: I’m sick of politics because (1) the Democrats are losing again and (2) I just got flamed by numerous people for blogging about why. After Bush took power in 2000, I resolved (for the sake of sanity) to forget about the state of the planet and concentrate exclusively on research. That led to probably the most productive period of my career. I may have to make a similar resolution today.
Comment #99 September 13th, 2008 at 6:21 pm
Mark: I believe that in spite of global warming, rising oil prices, ecosystem destruction, the decline of democracy in the US, etc., there’s a decent chance humans will somehow muddle through and the future will turn out OK. I’d vote that the most likely of my beliefs to seem ridiculous 50 years from now.
Comment #100 September 13th, 2008 at 6:28 pm
Are there any (classical) cryptographic algorithms which could not be cracked in polynomial time if P=NP?
Comment #101 September 13th, 2008 at 6:37 pm
I know Scott, the polls make me anxious and for me this kind of anxiety is the first time since I was not here in 2000.
I understand how you feel. But I just don’t want you to loose hope this time. I know it feels really bad to loose (especially with no solid reason) but for this country it is worth trying to win till the last minute.
You know all these things but I thought hearing from outsider might help 🙂
Comment #102 September 13th, 2008 at 6:38 pm
Are there any (classical) cryptographic algorithms which could not be cracked in polynomial time if P=NP?
Well, there’s the one-time pad, and other systems with information-theoretic security. But any (classical) cryptosystem based on computational assumptions could be cracked in polynomial time if P=NP.
Comment #103 September 13th, 2008 at 6:58 pm
S: (1) the Democrats are losing again and (2) I just got flamed by numerous people for blogging about why.
You asked a great and timely question, and people made some great points – What about that discussion equated with you getting “flamed”?
Comment #104 September 13th, 2008 at 7:12 pm
Also, I certainly hope I didn’t contribute to you being “flamed”. I don’t think it was anyone’s intention to ‘shut you up’ or suggest that you shouldn’t stump for something you believe in.
Comment #105 September 13th, 2008 at 7:13 pm
KJ: Well, I should’ve expected that people would react strongly—I used stronger language than I probably should have, and than I would have in a less agitated state.
Comment #106 September 13th, 2008 at 7:14 pm
KaoriBlue: No, don’t worry about—it’s not a problem at all.
Comment #107 September 13th, 2008 at 7:41 pm
Scott, you now have more data on how people might react and can choose to temper your language and speak when less agitated next time… on the other hand, you said what you said in the state that you were in and provoked a passionate debate among a group of intelligent people. Was there harm in that?
Comment #108 September 13th, 2008 at 7:45 pm
Was there harm in that?
No, probably not—I didn’t say there was! 🙂