Matrix Mult (you heard it here... third?)

(INNOVATIONS CONFERENCE: here)

(While preparing this two other bloggers wrote on the same topic, Scott here and Lipton/Regan here. Our slogan: Complexity Blog: You heard it here THIRD.)

Let w be the exponent for matrix mult. A very brief history of Matrix Multiplication (years given are years of publication, though it is odd to say Pan in 1978 showed that w < 2.796 since, for all I know, he did it in 1977 or even earlier.)

1. The obvious way to do this shows w ≤ 3. This is obvious to us; however, I wonder when it was first stated.
2. Strassen in 1969 showed w ≤ 2.808. This is important since it shows that Gaussian Elimination is not optimal (that is the name of the paper) and also because it is a cautionary tale for lower bounds- w=3 seems optimal... but its not!
3. Pan in 1978 showed that w < 2.796.
4. Bini, Capovani, Romani, Lotti in 1979 showed w < 2.78.
5. Schonhage in 1981 showed w < 2.522 This was significant since it used a brand new technique.
6. Romani in 1982 showed w < 2.517.
7. Coppersmith and Winograd in 1981 obtained w < 2.496. This was significant in that it broke the 2.5 barrier.
8. Strassen in 1986, using a very diff technique, obtained w < 2.479.
9. Coppersmith and Winograd in 1987 obtained w < 2.376. (See here for the Journal Version.) This paper uses the large 3-free sets of Behrend. (See here for Behrends article (it might now work- its the Proceedings of Nat Academy of Sciences website and I don't know if its free to ALL or just to some schools.) or here for my survey of large 3-free sets.)
10. Cohn and Umans in 2003 proposed a group theoretic approach which had the potential for new algorithms. Kleinberg and Szegedy in 2005 obtained new algorithms using the approach, but couldn't beat 2.376.
11. Elkin in 2008 (here) obtained larger 3-free sets than Behrends. Elkin in 2010 (here) used these sets to get a log^v improvement over CW for some v > 0.
12. Andy Stothers 2010 PhD thesis (here) claims to have w ≤ 2.374. The result was not stated in the abstract. He didn't post a preprint or email a blogger so this work was relatively unknown. He did tell some experts in the field. (See the comments on Scott's blog for what might be the full story on that).

Virginia Vassilevska Williams has obtained (ind of Stothers) w < 2.3727 (see here) with a very sophisticated analysis. How do I know its sophisticated? Because the paper is 71 pages long and looks scary.

1. This is clearly a breakthrough! There had been NO improvement in two decades!
2. The improvement is small; however, it may lead to more improvements (this seems to be common in this field).
3. Can Elkin's 3-free sets be used to get a log improvement over Virginia's result? Not sure we care- from what I understand (which is not much) (1) the current techniques can likely be pushed further, and (2) Elkin's 3-free sets will only give a log-ish improvement, no more. (Is log-ish a new word? Should it be?)
4. Is the algorithm practical? I suspect not.
5. Two breakthroughs in theory within a year from the same family. Impressive!

The Death of Complexity Classes?

In the 2011 Complexity proceedings there are three papers that analyze complexity classes, Ryan Williams' great paper on ACC, Russell Impagliazzo's paper on average versus worst case for NP and a Hartmut Klauck's paper on AM in communication complexity. That's the complexity conference. At STOC, there was only the Aaronson-Arkhipov paper on linear optics.

Complexity classes capture important aspects of problems based on how they can use various resources. The complexity zoo has nearly 500 classes. Many of the greatest theorems in theoretical computer science relate classes like NPSPACE = PSPACE, NL = co-NL, PH ⊆ P^#P, IP = PSPACE, NP = PCP(log n,1), SL = L, NEXP not in ACC and many others. The most important open question in our field (and maybe any field) is the relationships of the classes P and NP.

So why do we see so few papers about complexity classes these days? We are victims of our own successes and failures. We have succeeded in classifying and relating most of the connections between classes where we don't have relativizable counterexamples and have failed, outside of interactive proofs, to develop many tools that let us get around relativization and other barriers.

So here we sit, still putting out the occasional paper on complexity classes but mostly hitting a wall. Occasionally we see a nice breakthrough like Ryan's paper but mostly we are just clawing at that wall waiting for someone to create a wrecking ball so we can make real progress. 

The Jobs Bio

I just finished the Walter Isaacson biography of Steve Jobs. Seems like everyone in the blogosphere has analyzed every sentence in the book, so I won't do that.

Instead I viewed the book as a trip down memory lane. The Apple II was my second computer and while I never owned a Mac you can't avoid them in the CS community. My family has by now gone through a dozen or so iPod/iPhone/iPad devices.

The biography opens up the curtain and you get to see the man behind these devices. Jobs was not a computer scientist or even a computer engineer. He was a designer who understood computers enough to make them beautiful and make them work better. His simplicity sometimes goes too far, I like the context-sensitive menus from a right mouse button and often double click the one button on my iPhone instead of single click or vice-versa.

I found myself least interested in Jobs' personal life, most of the problems he dealt with were of his own doing. He wasn't a nice guy and often got upset with people who don't share his values. But he also knew how good technology should work and we're better off for it.

I love reading biographies of successful people, you really get to see a fuller picture both the good and the bad. Walter Isaacson's book is rather unique, rarely do we get such a complete picture so soon after his untimely death.

If Steve Jobs isn't your thing, try Isaacson's bio on Einstein instead, another great read.

Short Bits

Because some things are too long to tweet and too short for their own blog post.

What's the algorithm for the perfect sushi? Enjoy it with some cool refreshing SODA in Kyoto. Early registration deadline is December 20th and lots of travel support still available (apply by Nov 29).

What's new for STOC 2012 in New York City? An open call for workshops (apply by Dec 2) and a best student presentation award. Practice up. Please also nominate people for Gödel, Knuth and SIGACT Distinguished Service prizes.

Google scholar citations now open to all. Now you can see my papers at Google, Microsoft, ACM, DBLP and my own papers page. Google has the best stats and ranking, DBLP the best links, my page the most accessible downloads and Microsoft has the coolest graphics.

Google gives all the stats so we can rank job applicants. Why stop there? Google can use their magic algorithms to tell us who to hire. No more messy recommendation letters and awkward interviews.

Are these journals real?

Consider the following email I got:

Dear Professor,
 1. Antarctica Journal of Mathematics
 2. ArchimedesJournal of Mathematics
 3. BesselJournal of Mathematics
 We are charging only $3 per page,
 which is very cheap when compared to
 other money oriented journals.
 Further we request you to withdraw your paper,
 if you have already submitted it to any money
 oriented journal.  You can submit your research
 papers to our online journals.
 We also consider paper from
 Statistics and Computer Science.

What is going on here? Possibilities:

1. The journals are fake. They are part of an April Fool's Day joke. Using BesselJournal and ArchimedesJournal, with no space in the obvious place, (not typos by me- this is what the email said) might have been a clue that they were jokes.
2. The Antarctica journal is real and is a reaction to the notion that we shouldn't hold conferences or workshops in places where there are human rights violations. (See here.)
3. The Antarctica journal is real and is a reaction to the notion that whenever you have a conference the locals get to go cheap; this conference will be equally expensive to all (or to most). (See here.)
4. The journals are real. The Antarctica Journal of Mathematics was founded because all continents except Antarctica had journals and the founders thought this was unfair.

The last option is the correct one. I am not surprised- the journals have to be real since the titles are not quite funny enough to be a joke. Antarctica Journal of Mathematics sounds fictional, like The University of Southern North Dakota at Hoople, but it is not. The Antarctica Journal's website has real articles on it and seems to have been publishing since 2004.

In some fields it is standard to pay-to-publish. Older faculty used to tell me about page-charges for journals in our field, in much older times, (and I think grants mostly paid for it) but I have never seen them in my academic lifetime (in math and TCS). (Exception: a few conferences, though not many.) Different fields evolve in different ways, and I do not claim to know what the best approach is. However, since in our field (Math, TCS) it is standard to NOT have page-charges (I do not know of any journal that does this, and I know of only a few conferences that do) it seems odd to ask you to compare their journal with other money oriented journals. Are there other ones in mathematics?

Penn State

Take the state of Pennsylvania and draw the two diagonals. Where they cross is the small town of State College, home of the Pennsylvania State University. I first traveled to Penn State in 1989 on an interview trip. We went to dinner at the only nice restaurant near campus. The conversation turned to Joe Paterno, Penn State football coach. The waitress, a Penn State undergrad, said "Oh, you mean God."

As many of you know, Paterno and Penn State president Graham Spanier were fired last week in the wake of the Jerry Sandusky child sexual abuse scandal.

I have a certain affinity for Penn State.I have worked with researchers there from experimental economics to pure logic and they have a number of people there connected to my NEC days. I have been back to that campus several times most recently in the spring of 2010. The changes in those two decades have been amazing.

Quite a bit of new building on campus and off. There are now a number of nice restaurants near campus. There are plenty of new buildings on campus too including a beautiful IST (Information Sciences and Technology) building that houses the IST and CSE departments. Just in theoretical computer science, Penn State made some recent strong hires and had a rare double PECASE win of Adam Smith and Sean Hallgren.

Paterno helped build the Penn State brand through football which he coached at Penn State since I was a toddler. Paterno also knew that Penn State meant academics as well, he had a large number of academic all-Americans on his team and donated money for a library on campus that bears his name. Spanier build on this brand to develop real growth in the university and the town it lives in.

Paterno and Spanier should have done more to protect the children but I hated to see them leave under these circumstances. They have both done much for Penn State and not just on the football field.

My response to the Gasarch P vs NP poll

A while back GASARCH solicited responses to a P vs NP poll and gave Oct 31 as the deadline. Now that the deadline is passed I post my answers.

1. Does P=NP? I think P is NOT NP. However, I am not dogmatic on this. When I first saw the Graph Minor Theorem used to get Vertex Cover for fixed k into O(n³) times I thought that a different very-hard-math-thing-that-I-don't-understand might be able to get SAT in P. Also, I am more convinced that separating the two is hard then I am convinced that they are different. Litmus test: If someone told me that the problem had been solved, but not which direction, I would guess P=NP. SIDE NOTE: My wife thinks P is NOT NP since If P=NP then they would have proven it by now. This argument may become more compelling as time goes on.
2. When do you think it will be resolved? Between 200 and 400 years from now. Jon Katz told me: If its not solved within 200 years its not going to be solved..
3. What kinds of techniques will be used?
   1. Fermat didn't know about Elliptic Curves. Similarly, we do not know the techniques.
   2. I hope its Ramsey Theory and Logic so I might understand the proof.
   3. If it comes out of Geometric Complexity Theory I will not understand the proof.
   4. We will show that P ≠ NP by showing that FACTORING is not in P. SAT might not be a good candidate for separation. This kind of thing has happened before (once): The proof that AC₀ ≠ NC₁ was done by showing PARITY not in AC₀. PARITY is not complete for NC₁ under AC₀ reduction. The word problem for S₅ is, but was not useful for separation. Factoring may be a better candidate for separation since you can generate instances that seem hard, where for SAT this seems hard to do.
   5. Ryan Williams great result shows that there are still things we can do with what we know now. Is P vs NP one of them? NO.
4. Will the problem still be relevant given advances in SAT solvers? YES. Sat Solvers are GREAT and can solve lots of things- perhaps more than we had thought. But there are still lots that are not. The 17x17 problems has resisted attempts by SAT solvers to solve it (or so I've been told). The problem is a 4-CNF with 4 × 17² vars (not that many), and roughly 4 × 17⁴clauses (too many).
5. Feel Free to comment on other things:
   1. Graph Isomorphism: We will show P ≠ NP but still not know the status of GI. OR we could find that GI is in P tomorrow.
   2. As noted above, we will show Factoring is NOT in P.
   3. Quantum Computers will never be practical; however, see next note.
   4. Just as the Prob Method is now a STANDARD thing to know even if you are not working on probability, Quantum methods will be a standard thing to know even if you don't work on quantum computing.
   5. We will show L=RL before I do this poll again.
   6. Within 10 years all supermarkets will have self-checkouts that work nicely and that you are expected to use--- except in New Jersey which will outlaw them to create more jobs (as they do now for self-service gas).

Making Money the (Computationally) Hard Way

Digital cash systems have come and gone but Bitcoin seems to be doing okay. By request I am giving a lecture about Bitcoin in my crypto class. Most of the material I find about Bitcoin is either very high level for a typical user or very low-level detail for the implementer. In this post I'll try to hit the middle ground.

Bitcoin tries a different approach to digital case. Their goal is not anonymity but more a cash system that works in a peer-to-peer network without a central authority.

The basics of Bitcoin come from a paper by the mysterious Satoshi Nakamoto. The Bitcoin systems doesn't use encryption but it does make strong use of secure hash functions and digital signatures. A user establishes an account by creating public and private keys for an elliptic-curve based signature scheme. A hash of the public key serves as the account number.

A transaction from person A to B roughly consists of the amount, a link to an earlier transaction where A received bitcoins, B's account number, A's public key and A's signature of all of the above. Transactions are transmitted to everyone. More general transactions are also possible.

Transactions aren't accepted until they appear in a block. A block consists of a hash-tree of transactions, an extra transaction giving 50 bitcoins to the block creator (this will decrease over time), a hash of the previous block, a time stamp and something called a nonce. The nonce is just an extra number chosen so that the hash of the block has a certain number of zeros in the right place.

You create money by creating blocks which requires finding the right nonce, a computationally difficult task. The number of zeros is set so that a new block is created on average every ten minutes. A transaction is accepted when there is a chain of six block starting with the one where the transaction occurs. This prevents double spending as that firmly establishes this chain as the "official" one.

There's a lot more details but the idea is a clever use of computation to mine money like one can mine gold with considerable effort. Or you can get money by trading goods or services (or real currency).

Not clear to me that it could scale for wide-spread use but still quite a clever and so far working system.

The Annual Fall Jobs Post

For these looking for an academic job in computer science next year, best to start on the jobs pages of the CRA and the ACM. Both lists seem long this year, perhaps the job market is finally beginning to pick up.
Also check out the postdoc opportunities on Theory Announcements.

Feel free to list other job opportunities in the comments.

My department has two faculty positions for next year. Neither one specifically in theoretical computer science but we do plan to treat the areas broadly.

My advice: Apply widely, the job market is quite unpredictable. Put real effort into your research statement and be sure your CV is informative yet concise. Most importantly: Choose your letter writers well.

Journals

What is the purpose of an academic journal? To provide a permanent vetted record of a specific research endeavor.

The ways we communicate scientific research has vastly improved, particularly with the advent of the Internet, but the need for that basic mission will never go away.

Noam Nisan laments that journals do not provide a quick form of dissemination or do the proper amount of vetting. He's correct on both points. Computer scientists need to take journals more seriously to improve the vetting process and the speed to publication. But also journals have never played the role of quick dissemination in computer science. That role has been taken by conferences, departmental technical reports and more recently on-line archives. Journals don't compete with sites like ArXiv, they play different roles.

Tim Gowers suggests a commenting/scoring system for reviewing papers. I'd love to see such a system built into ArXiv and ECCC. But it won't supplant the need for academic journals. Most papers won't get reviewed and most researchers won't review papers. Collaborative projects like Wikipedia, Polymath, Math Overflow (and the TCS descendant) are incredible resources but just a small number of researchers are significantly involved. If you reward people for reviewing papers (through reputation or otherwise) then people can decide not to review guilt free. 

We are moving to a world where we rank research papers not on where they appear but by how many citations they achieve, a statistic the Internet has made easier to measure. One can cite an ArXiv paper just as easily as a JACM paper. The incentives for an author to do more than throw up a paper on an on-line site are going away. We will no longer fulfill the mission of journals and future scientists will struggle understanding the how and why of what we did. Is this the gift we want to leave to the next generation?