Simons postdoc: call for applications
Anyone who feared that my taking a real job would lead to the slow demise of this blog: your fears were entirely justified. I barely even read blogs anymore—or Twitters, or whatever the young people use nowadays. Though come to think of it, maybe I should switch to a Twitter feed, since blogging has become too weighty and substantive for me?
In the meantime, I’ve been asked to post the following.
Simons Postdoctoral Fellowship at the Massachusetts Institute of Technology in Theoretical Computer Science
The Theory of Computation (TOC) group at the Computer Science and Artificial Intelligence Laboratory (CSAIL) at MIT is seeking candidates for a post-doctoral position in the general area of the theory of computation. Applicants in all areas of theory are encouraged to apply, including (but not exclusive to) algorithms, complexity theory, combinatorial optimization, cryptography, distributed computing, game theory and computation, geometry, parallel computing, and quantum computing. This fellowship is made possible by a generous gift from the Simons Foundation.
The fellowship is a two year position, starting the summer or fall of 2010. The fellowship stipend is gauged to attract the highest caliber of applicants. Generous funds for scientific travel will be available for use at the fellow’s discretion. Fellows will be assigned a faculty member close to their research interests from the TOC group. Fellows will be encouraged (although not required) to teach a graduate seminar in their area of research.
- Eligibility: Candidates must receive their PhD during the academic year immediately preceding that in which the fellowship would begin. There are no other restrictions based on nationality or any other basis.
- Application Process: Candidate applications should include a description of professional interests and goals in research. Each application should include a curriculum vitae and the names and addresses of three or more individuals who will provide letters of recommendation. Letter writers should submit their letters directly to MIT to the address below. Please submit complete applications by January 31st, 2010.
- Address to submit application: All application materials and recommendation letters should be sent electronically to theory-postdoc@csail.mit.edu. The candidates name should be included in the subject line of the email. Alternatively, the materials can be also sent to the following address:Simons Postdoctoral Fellowship, c/o Joanne Hanley
MIT Computer Science and Artificial Intelligence Laboratory
The Stata Center, Building 32 –G682
32 Vassar Street
Cambridge, MA 02139, USA.
Follow
Comment #1 December 9th, 2009 at 4:12 pm
Twitter is probably more productive since it “decreases fragmentation”. But on the other hand what will happen to the type of in-depth, yet accessible, CS posts? Maybe you’re just getting to follow too high a standard and requiring too much of what you write.
Thankfully i haven’t gotten to that point yet so i don’t mind sharing that over the past couple of weeks i’ve been building polynomial algorithms for NP-Complete problems. Yes, I built 3 polynomial algorithms that run under O(n^4) and ran them side by side with a brute force algorithm, in instances of size up to 35 nodes to check just how bad they are. They all start with a low error rate which increases fast and i imagine eventually reach 99.9…%.
The best i got was a randomized algorithm, which stays under a 40% error rate up to 33 nodes. Unfortunately i’m reaching a point where my brute force implementation can’t realistically run on my laptop. I’d like to know what’s the best known algorithm for NP-Complete problems? Meaning, which one has the best ratio of run-time, memory consumption, input range and error rate? For example, if there’s a low exponential-time algorithm out there with a significant input range and low error rate, even though it’s exponential, i would still find it quite valuable.
I want something that will run on my laptop (say solve a large sudoku), in no more than a few minutes, for the greatest possible input size and with the lowest possible error rate.
I have an O(n^4) time, O(n) space, 40% error rate algorithm for instances up to 33 nodes and i think i can get it up to O(n^4) time, O(n) space, 25% error rate for instances of up to 35 or more by this week. Impressive? No, but can you do better?
Comment #2 December 9th, 2009 at 4:41 pm
Job, what problem are you talking about? You are welcome to try my Qualex-MS for max clique (downloadable from my home page :))
Comment #3 December 9th, 2009 at 5:00 pm
Stas, actually it’s the clique problem i’ve been using, so i’m interested in your Qualex-MS. I don’t use the DIMACS format you mention (first time i hear about it, glad i posted) i encode graphs as integers (one bit per edge) where every int is a valid graph – makes generating random graphs really easy – but i should be able to plugin to your solver and find out how my peasant algorithms are doing.
Comment #4 December 9th, 2009 at 5:17 pm
DIMACS binary format is also a packed bitwise representation of edges. cliquer has a nice C library to work with DIMACS formats (both binary and text.)
Comment #5 December 9th, 2009 at 5:22 pm
Round 1, Stas’ Qualex-MX solver versus Job’s Router solver. Stay tuned. 🙂
Comment #6 December 9th, 2009 at 11:05 pm
Hm, maybe following other blogs is why I’ve been sub-obtimally productive this past couple of weeks. I mean, I haven’t even needed Shtetl-Optimized as a procrastinating device ;).
Comment #7 December 10th, 2009 at 1:04 am
Shouldn’t we expect a post on this google-dwave collaboration?
http://googleresearch.blogspot.com/2009/12/machine-learning-with-quantum.html
Comment #8 December 10th, 2009 at 2:15 am
Hey Scott
I am not a big expert on Quantum Computing, so I’d be very grateful on your opinion about this article claiming a very practical use of adiabatic computing
http://googleresearch.blogspot.com/2009/12/machine-learning-with-quantum.html
Comment #9 December 10th, 2009 at 2:39 am
GitOuttaHere! DWave still exists?
Comment #10 December 10th, 2009 at 3:26 am
What’s the real job?
Comment #11 December 10th, 2009 at 4:12 am
Stas, how does your Qualex-MX handle small instances? I’m convinced i have the DIMACS encoding right, yet when i feed it a 9-clique it tells me the max clique size is >=32. 😛
I’m looking for an algorithm that, when running randomly over an interval of instances of size 0 to x, will return the highest clique size with high probability, where x is up to 50 for example.
Comment #12 December 10th, 2009 at 7:21 am
Job, could you check your 9-clique instance with cliquer? Or you can use the original DIMACS converters to get your instance in text format and check the clique manually: DIMACS FTP site.
There are no bugs in Qualex-MS known to me, the only issue is if you compile it with old LAPACK, it hangs sometimes in the eigendecomposition routine. So, I guess there is something wrong with your instance…
Comment #13 December 10th, 2009 at 10:43 am
Hi Raoul, if you’d like to see what we’ve been working on there are a large number of links to publications and presentations organized by research areas in the sidebar off this page http://dwave.wordpress.com/system-overview/ .
Comment #14 December 10th, 2009 at 12:44 pm
Geordie, i signed up for the D-Wave web services. As you can see above i’m looking for Max Clique solvers and i’ve just noticed that you have one available on your web service. After i’m done checking Stas’ implementation, i’ll check out D-Wave’s. I don’t have any real benchmarking purpose i just want to see what everyone is doing and learn something.
Round 2 – D-Wave’s solver versus Job’s Router vs Stas’ Qualex-MS solver. Stay tuned 🙂
Comment #15 December 10th, 2009 at 1:01 pm
Raoul
D-Wave exists, you are right, but now Google Research says that D-Wave does the right thing and quantum adiabatic computers are used to do large-scale image processing. I doubt that quantum computers can be practically used but my expertise is not enough to be sure about that. From another point of view, Google Research sounds as authoritative source…well maybe
That’s why I want to know Scott opinion about this article.
Comment #16 December 10th, 2009 at 1:28 pm
Geordie,
Sorry about the wisecrack, that’s why one should not post in the middle of the night. I have no solid opinion other than a hunch that practical applications of QC will forever stay a couple of years away.
To support this hunch, I will bet $1.75 that: QC will NEVER do half of what the 2009 claims for it are. Can anyone provide a short list of the usual QC claims, so I will know when I have to pay off?
For more fun, here is another bet, one a bit easier to decide if I have to pay off: I, Raoul Ohio, will bet $2.75 that a human being will NEVER travel to Mars, pick up a rock, and return alive to Earth with the rock.
Comment #17 December 10th, 2009 at 3:01 pm
Why do universities hire post docs btw ? This is not a criticism. I am just curious in knowing the reasoning that univ. have for offering such positions.
My argument against offering such positions is that I believe that the goal of univs. is to provide an environment to create knowledge, create people who can create knowledge and create tools which can further improves understanding of […].
A univ awards a degree when they believe that by awarding a degree, in some sense, helps them towards attaining their objectives. A post doc is not a degree. It straight away means that univ. got nothing to do with them. Why do we call it as a “post doc” when it is not a degree anyways ? Had univ offered two doctorates instead, it would have contributed more to the society (in terms of people and knowledge created). Rather by offering such positions univs. are taking away the freshness of mind of fresh PhDs. Which otherwise could have been helpful had he joined some other univ. as a prof(well there are many univ in the world who need such peoples). Do funding agencies believe that univs. are places of high quality but cheap labor.
Comment #18 December 10th, 2009 at 4:17 pm
Hi Job, I would be very interested in finding out if our Max Clique solvers are competitive with the others you are trying. If you need help with anything let me know and I’ll get someone to help you.
Comment #19 December 10th, 2009 at 10:05 pm
Scott,
I immensely enjoyed reading the Great Ideas in Theoretical Computer Science lecture notes over my recent Palm Springs vacation.
If you’ve come to the point where you refer to “young people”, then you probably also recognize silence is a powerful tool in your toolbox.
Comment #20 December 11th, 2009 at 5:20 am
Stas, yesterday i tested your Qualex-MS solver and it’s remarkably fast and reliable. I couldn’t catch it giving a single wrong answer.
While i sense that there’s lots of room for improvement on my side since (i’m only up to +15% error rate at +40 nodes) i’m amazed that your implementation does so well. What’s the theory behind Qualex-MS? How does its error rate evolve over time and what’s the smallest graph that causes it to give the wrong answer?
Comment #21 December 11th, 2009 at 9:38 am
” slow demise of this blog ” ?
Maybe you just needed some information on which to react.
Here is one, Google is working with D-Wave:
http://googleresearch.blogspot.com/2009/12/machine-learning-with-quantum.html
Comment #22 December 11th, 2009 at 4:10 pm
Since when is being a professor a “real job”?
Comment #23 December 11th, 2009 at 6:04 pm
Here’s the “Clique Solver” contest format:
Participants:
Cliquer – http://users.tkk.fi/pat/cliquer.html
Qualex MS – http://www.stasbusygin.org/
DWave – https://apps.dwavesys.com/orionui/
Each algorithm is run 10,000 times split evenly between random instances of size 200-300. Algorithm A “wins” round X if it finds a higher clique than Algorithm B, for graph instance X.
The implementation that wins the most rounds wins. 🙂
I’m running tests in the following order:
1. Cliquer Vs Qualex MS
2. DWave Vs [Winner of 1]
Sound good? 🙂
Comment #24 December 11th, 2009 at 7:31 pm
Cliquer found larger cliques ~15% of the time (for instances between 200-300 nodes). Qualex MS was always equal to or under.
I’m going to run Cliquer vs DWave’s _software_ solver since there isn’t a Quantum solver available yet.
It’s not nearly as exciting this way, but i’ll do it anyway.
Comment #25 December 11th, 2009 at 10:32 pm
Hi Job, my detailed reply to your questions about Qualex-MS got suspected to be spam and went to moderation queue three times 🙂 . So, I won’t attempt to send it again before Scott clears me from being flagged. For now, just download the paper “A New Trust Region…” from my website, the answers to your questions are there.
Also, of course cliquer always finds exact solutions – it’s an exact solver. If your interest is in instances for which you don’t have to wait cliquer for too long, it’s your best choice 🙂
Comment #26 December 11th, 2009 at 11:49 pm
Ah, i didn’t realize Cliquer was an exact solver, but now that i bumped the tests to 600 nodes it does begin taking longer than a minute per instance – which is still amazing considering the graph size – versus ~4 seconds for Qualex MS.
Comment #27 December 12th, 2009 at 2:41 am
Scott
Please, once again…could you, please evaluate the claim that quantum adiabatic computing is used for practical large scale image processing. I am very curious is this true or not. I’ve seen high interest from many people to this topic, but I’ve not seen expert evaluation of this claim.
Comment #28 December 12th, 2009 at 8:11 pm
Congrats. My sense is Obama’s election and technocratic governance has also played a role. You’re a talented blogger, but I’ll refrain from wishing you downsized or a Palin win in ’12.
Comment #29 December 13th, 2009 at 8:17 pm
Stas, here’s the smallest graph that i could find so far, for which Qualex MS returns a less-than-maximum clique size (returns 4 instead of 5):
http://www.bloo.us/graphics/qualex-ms-flaw-minimal/render/
For different, random orderings of this graph, F, Qualex-MS succeeds (for those that i tried).
I also tried merging F with non-complete graphs of 5 nodes and the majority of the resulting graphs still cause Qualex-MS to return a less-than-maximum clique size.
Finally, by adding a node N to F, such that N is connected to all nodes in F, we obtain a graph that still causes Qualex-MS to return a less-than-maximum clique size, this time increased by 1. This process can be repeated multiple times with the same result (i tried 100 times).
I’ve seen these two behaviors in my more elementary algorithms as well. I’m guessing that given a graph G that “breaks” a non-randomized algorithm M, we can generate an arbitrary amount of graphs that also break M, by successively:
1. Merging with any graph not containing a k-clique.
2. Introducing a new node N such that N has maximum degree.
Does this mean that if any non-randomized, polynomial time algorithm M has at least one flaw (returns the incorrect answer for a given graph F) then that algorithm has a >99% error rate for instances of size > E for large enough E?
Comment #30 December 13th, 2009 at 11:18 pm
^ Of course not. Suppose you had some hard instance I. The instances that your construction would generate all have I has a subgraph, which will only be a tiny fraction of large graphs (assuming I is nontrivial)
Comment #31 December 14th, 2009 at 6:49 am
Right, of course, i was jumping to conclusions as usual.
Comment #32 December 14th, 2009 at 8:30 am
Job, yes, I previously found two 16-vertex instances where Qualex-MS failed to find 5-vertex max clique and was not able to find any smaller counterexample. Then the rate of success starts falling slowly with instances of more than 16 vertices.
Adding a new vertex connected to every other vertex doesn’t change anything – Qualex-MS catches such things at the preprocessing stage and pre-selects vertices that must be in max clique by being non-connected only to a subset of total weight not greater than the vertex itself. In the unweighted case it means being connected to \geq n-1 vertices.
Comment #33 December 14th, 2009 at 4:50 pm
Stas, in the graph i linked above, Qualex-MS returns 4 as the max clique size, rather than 5. When i introduce a node that’s connected to all nodes in the graph, Qualex-MS returns 5, rather than 6:
http://www.bloo.us/graphics/qualex-ms-flaw-add-node/render/
This can be repeated multiple times with the same effect.
Comment #34 December 14th, 2009 at 5:01 pm
Exactly, the new node is preselected to be in the clique during preprocessing and then it is deleted and the algorithm ends up with your original graph. Of course, the resulting clique size gets bigger by one.
Comment #35 December 14th, 2009 at 5:08 pm
Ah, makes sense, thanks.
Comment #36 December 16th, 2009 at 4:38 am
Google, D-Wave and Quantum Computing for image recognitions is in New Scientists
http://www.newscientist.com/article/dn18272-google-demonstrates-quantum-computer-image-search.html
Comment #37 December 16th, 2009 at 4:49 am
http://www.ditii.com/2009/12/11/google-demos-quantum-computer-at-nips-2009/
While quantum mechanics has been foundational to theories of physics for about a hundred years picture of reality it paints remains enigmatic. Google gives an e.g. “Assume a ball is hide in a cabinet with million drawers. On average it’ll take you 500,000 peeks to find ball. Now a quantum computer can perform such a search looking only into 1000 drawers.”
Comment #38 December 16th, 2009 at 10:29 pm
Because $O(\sqrt{n})$ means “exactly the square root of n operations”.