Complexity Theorem of the year goes to Ryan Williams for his exciting separation of NEXP from ACC0. The runner up is Arora, Barak and Steurer for their algorithm for unique games. Also some great progress on some of Bill's favorite questions including Arithmetic Progressions and the Erdos Distance Problem.
None of these papers got mentioned in the New York Times so the most notable paper of the year goes to Deolalikar's P ≠ NP. Many of you got upset that I didn't give this paper the respect it didn't deserve. I did appreciate the publicity the paper generated for our great open problem but the status of the P versus NP question remains: still open.
Last year we highlighted several new blogs. This year the trend is reversing as several theory bloggers have slowed down or stopped blogging. A few of our commentors got very ugly on our blog this year and finally we have given in to comment moderation, though we rarely block.
But social networking in the theory community continues on in other ways highlighted by the Theoretical Computer Science Q&A site. The SIGACT Facebook and Twitter pages have well over a hundred followers each.
The jury is still out on how a near complete change of NSF personnel and the fall elections will affect funding for theoretical computer science. We can always hope.
In this year I started a discussion on remaking STOC. The most popular thing I ever wrote is now this tweet. And don't forget my daughter Molly and her friend Danielle as NP and P.
Gone but not forgotten: Martin Gardner, Joseph Kruskal, Avner Magen, Benoît Mandelbrot, Robin Milner, Partha Niyogi, Sam Roweis and Numb3rs.
Thanks much to our guest posters: Daniel Apon, Paul Beame, Rance Cleveland, Ben Fulton, Josh Grochow, M.T. Hajiaghayi, Bernhard Haeupler, Nicole Immorlica, Subrahmanyam Kalyanasundaram, Clyde Kruskal, Michael Mitzenmacher, Rahul Santhanam, Aaron Sterling, Richard Taylor and Vijay Vazirani. We also thank guest photographer Evan Golub.
Looking forward to 2011 with the big FCRC meeting, learning the location for the Simons Institute for the Theory of Computing and just maybe I'll finish writing my P versus NP book (a bit more than half finished).
Of exceptionally broad interest in 2010 to mathematicians, scientists and engineers has been Scott Aaronson's and Alex Arkhipov's Computational Complexity of Linear Optics (CCOLO) ... both Scott and Alex's (evolving) presentation of this work, and our increasing appreciation (as engineers) of its significance (and beauty).
ReplyDeleteMoreover, our QSE Group's thanks are extended to all the math bloggers whose efforts are helping to make broad-spectrum appreciation of CS/CT/QIT feasible ... you are playing a central role in helping our 21st century to be a wonderful one.
Since you have mentioned the Simons Institute for the Theory of Computing, is it known who went to the 2nd round of the selection process for the location of the Simons Institute for the Theory of Computing?
ReplyDeletefinally we have given in to comment moderation
ReplyDeleteAnd there was much rejoicing!
The SIGACT Facebook and Twitter pages have well over a hundred followers each.
I think @cstheory deserves a big mention here. A very convenient way to follow most of the theory blogs without having to track them individually.
I loved Al Gore's response to that silly rumor (the truth of which was that he said, correctly, that he backed the bill that made the internet public):
ReplyDelete"I was pretty tired when I made that comment because I had been up very late the night before inventing the camcorder."
Also, thanks for another year of wonderful blog posts!
Wasn't the comment, "During my service in the United States Congress, I took the initiative in creating the Internet."
ReplyDeletemade the internet public?
ReplyDeletedo you mean when it was made "legal" to have commercial traffic go over it?
If memory serves, Congressman Boucher took the initiative, wrote the bill, deserves a lot of credit, for the Internet being made more open to the type of traffic that made it more useful to the public and making it the "Internet" rather than the ARPANET or the NSFnet.
ReplyDeleteIn 2010, Lance wrote a highly enjoyable essay The Enduring Legacy of the Turing Machine, for the ACM Ubiquity Symposium What is Computation?.
ReplyDeleteLance's essay was enjoyable (to me) because every individual sentence of it is so "obviously true" ... and yet, the conclusion reached is so thoroughly disagreeable. Dang!
Lance's agreeable reasoning was (in brief):
----------
The Church-Turing postulates: Computation is about process, about the transitions made from one state of the machine to another. Computation is not about the input and the output, point A and point B, but the journey.
----------
Lance's broad (too broad IMHO) conclusion was:
----------
The Church-Turing thesis: Everything computable is computable by a Turing machine.
----------
Gosh ... it would be a shame if we were to arrive at the end of the 21st century, without having to modify this thesis.
Yet on the other hand, the reasoning of Lance's essay (and of Dave Bacon's essay too, in the same ACM symposium) is sufficiently clear and compelling, that it's not so obvious what modifications to the CT are feasible.
Hmmmm ... let's experiment with (minimally) restricting both the CT postulates and the CT conclusion, so as to bring them into better accord with the real-world practices in science and engineering (added words are in italics):
----------
Restricted Church-Turing postulates: Computation is about separable processes, about the transitions made from one state of the machine to another. Computation is not about the input and the output, point A and point B, but the verifiable journey (that is, computation is about verifiable computational trajectories).
----------
The restriction separable is applied in order to distinguish computation from sensing. In modern quantum sensors (spin microscopes, photon number detectors) the presence of the sensor inseparably modifies the dynamics of the system being observed; thus it is convenient to define computation to be that class of processes whose dynamics are independent of the system being observed (or simulated). Thus separability is a strong (yet natural) restriction to impose upon computational processes.
The restriction verifiable is applied because the class of Turing machines includes some machines that are so powerful as to be beyond finite comprehension, in the sense that the languages they accept (in PTIME) are forever beyond our capacity to verify, even in principle. Thus verifiability too is a strong (yet natural) restriction to impose upon computational processes.
Thus we are led, via pragmatic science-and-engineeering considerations, to (minimally) adjust the Church-Turing thesis to read as follows:
----------
A restricted Church-Turing thesis: Everything that is verifiably computable is separably computable by a Turing machine.
----------
There is a simulation-centric version of the C-T thesis that is even stronger:
----------
A restricted Church-Turing simulation thesis: Every separable physical process is verifiably simulatable by a Turing machine in P.
----------
The addition of the phrase "in P" is inspired largely by Robert Bixby's article Solving real-world linear programs: a decade and more of progress, which documents faster-than-Moore progress in the capabilities of broad classes of algorithms ... and there is no end in sight for these increasing capabilities. Good! :)
To my knowledge, the above is the strongest version of the Church-Turing thesis that has been proposed ... hence it is the easiest version of the CT to falsify.
Lance and Bill, thanks for a great blog, that so enjoyably focusses upon this wonderful class of questions, which are of fundamental, practical, and abiding interest to the entire STEM community!