Sandy Extension

The deadline for submissions to STOC has been extended to Monday, Nov 5 2012 5:00 p.m. EST. 

Fall Jobs Post

Time again for the annual fall jobs post. As always the best places to look for academic CS positions are the job sites at the CRA and the ACM. Also check out the postdoc and other opportunities on the Theory Announcements site. It never hurts to check out the webpages of departments you might want to be at or to contact people to see if positions are available.

I encourage everyone who has a job to offer in theoretical computer science at any level to post links in the comments.

With computer science enrollments expanding and the economy slowing recovering, I'm expecting quite an increase in the number of tenure-track jobs in computer science this year. On the other hand I'm expecting a decrease in the number of new postdoc positions though maybe more overseas.

Good luck to everyone in the market.

Planarizing Gadgets for Perfect Matching do not Exist!

At Dagstuhl I was delighted when I saw the title of a talk to be given Planarizing Gadgets for Perfect Matching do not Exist because I had asked the question about a gadget for planar Ham Cycle here. I was hoping to ask the authors if there techniques could be used to show that there was not Planarizing gadget for Ham Cycle (NOTE- I had either forgot or never knew that this was already known and was posted as an answer to my query to cstheory stackexchange, here.)

The paper Planarizing Gadgets for Perfect Matching do not Exist (or if you can get to it the MFCS 2012 version here) is by Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, and Thomas Thierauf. The talk was given by Jochen and was excellent.

Perfect matching is in P (Edmonds 1965) but is it in NC? Not known--- however it is in RNC (Mulmuley, Vazirani, Vazirani 1987). What about Planar graphs? They are different--- counting the number of perfect matching in a graph is Sharp-P complete (Valiant 1979) but counting the number of perfect matchings in a planar graph is in NC (Vazirani 1989). So of course Planar Graph Matching is in NC. Can we use this to get Graph Matching in NC? perhaps be a reduction? This would be neat since we would be using a reduction to prove a problem EASY rather than to prove a problem HARD. (I think this has been done before but is rare-- readers, if you know a case comment on it.) Perhaps there is some planarizing gadget: given a graph G use some gadgets to get rid of crossings and produce a planar graph G' such that G has a perfect matching iff G' has a perfect matching. That would be AWESOME! However, from the very title of the paper, we can guess this is not true. This paper shows that something AWESOME is not possible! A downer but worth knowing.

Jochen proved this and then went on to say that they had done the same thing for HAM CYCLE! That is, there is no planarization gadget for Ham cycle! (He also acknowledged that this was already known independently.) SO I didn't get to ask my question since they already had answered it. Great!

1. Their interest in planarization was related to an OPEN problem--- is Graph Matching in NC? By contrast my interest in Planarization gadgets for Ham Cycle was pedagogical--- I was in search of a better proof that Planar Ham Cycle is NPC- though there is no new theorem here.
   
2. I am delighted to know the result!
   
3. Their results says that a certain type of reduction won't work. Might some other reduction work? My sense is this is unlikely.
   
4. So--- is Graph Matching in NC? Since I believe NC=RNC I think yes. Will it be proven by showing NC=RNC or will it be proven directly (leaving NC=RNC open)? Or will the ideas that lead to Graph Matching in NC help to show NC=RNC? This is one of those questions that might be solved within a decade, as opposed to P vs NP which won't be resolved for quite some time.
   

Song of the Complexity Classes

I tweeted the audio of this song last week and here is the video. Recorded at Dagstuhl on October 18th. Written by Fred Green who also plays piano. Performed by David Barrington with Steve Fenner on chorus.

Fred gives apologies to Gilbert and Sullivan, the Complexity Zoo, and Tom Lehrer



Lyrics by Fred Green, copyright 2012

To the tune of "I Am the Very Model of a Modern Major General"

There's P and NP, BPP and ZPP and coNP,
And TC0 and AC0 and NC1 and ACC,
There's PSPACE, LOGSPACE, PPSPACE and ESPACE, EXPSPACE, IPP,
And LIN and L and Q and R, and E, EE and E-E-E.
There's SPARSE and TALLY, PL, P/Poly, NP/poly,
There's PromiseP and PromiseBPP and PromiseBQP,
There's FewP, UP, QP, UE, N-E-E, N-E-E-E,
And EXP and NEXP, FewEXP, and NE-EXP, and also Max-N-P.
  And EXP and NEXP, FewEXP, and NE-EXP, and also Max-N-P
  And EXP and NEXP, FewEXP, and NE-EXP, and also Max-N-P
  And EXP and NEXP, FewEXP, and NE-EXP, and also Max-N, Max-N-P.
There's Sigma_nP, Delta_nP, Theta_nP, Pi_nP,
We know BPP's in Sigma_2P intersection Pi_2P.
And NP to the NP to the NP to the NP
To the NP to the NP, that's the pol-y-nom-yal hierarchy!

There's #P, gapP, PP, coC=P and MidBitP,
And ModP, Mod_kP, Mod_kL, ParityP, MPC,
There's FNP, NPSV, NPMV, and SAC,
SAC0, SAC1, SZKn and SPP.
There's BQP and DQP and EQP and NQP,
And RQP and VQP and YQP and ZQP,
And BPQP, FBQP, ZBQP, QRG,
QAC0, QNC0, QNC1, Q-A-C-C.
   QAC0, QNC0, QNC1, Q-A-C-C
   QAC0, QNC0, QNC1, Q-A-C-C
   QAC0, QNC0, QNC1, Q-A-C, A-C-C
There's QSZK, QMA and QAM and QIP,
And IP, MIP, QMIP and also PCP,
And PPPad and PPcc, PSK and PQUERY,
And PP to the PP, PExp, PPA and PPP.

These complexity classes are
the ones that come to mind,
And there may be many others but they
haven't been defined.

Short Announcements

With a shout out to the friendly folks attending FOCS this week, some short announcements.

Read the STOC CFP before you submit the paper. There are significant changes to the submission format and procedure. Deadline is November 2.

Complexity will be co-located with STOC in 2013. Submission deadline is November 30.

The new Simons Institute for the Theory of Computing has a call for workshop proposals and research fellowships.

There will be a symposium to celebrate a new professorship named after SIGACT and STOC founder Patrick Fischer at Michigan on November 5 and a celebration of the 80th birthday of Joe Traub on November 9th at Columbia.

Dagstuhl Typecast

Nerd Shot from Dagstuhl Seminar 12421

Lance: Welcome to another Typecast from beautiful Schloss Dagstuhl. I’m here with Bill for the Workshop on Algebraic and Combinatorial Methods in Computational Complexity.

Bill: Beautiful? I thought this place was designed to be ugly so that we actually get work done.

Lance: So what work did you get done today, BIll?

Bill: I watched the debate. And you?

Lance: Steve Fenner and I came up with the easiest to describe PSPACE-complete problem ever!

Bill: Was it one of those poset things that you and Steve’s students work on.

Lance: A generalization of poset games but easier to describe. But we are getting off topic...

Bill: as did Obama and Mitt.

Lance: Bill my two minutes aren’t up yet. Anyway you’ll have to read about this new PSPACE-complete problem in a future post.

Bill: Since you didn’t ask, let me tell you about my favorite talk, Rank bounds for design matrices and applications by new Rutgers professor Shubhangi Saraf (Powerpoint). Despite the awful title

Lance: which is why I skipped that talk

Bill: it used complexity theory techniques to prove new things in math, a generalization of the Sylvester-Gallai theorem. You have n points on the plane...

Lance: Wait Bill, It will take longer to tell the S-G theorem than it would have to explain the new PSPACE-complete problem!

[Steve Fenner shows up with beer in hand. He goes off to get Lance one too.]

Bill: OK, I’ll leave this for a later post. What was your favorite talk?

Lance: Believe it or not it was an algorithms talk. Atri Rudra gave a very simple algorithm to do a join operation motivated by reconstructing 3-d collections of points from projections. [Powerpoint]

Bill: Yes, and it may have applications to complexity as most real world algorithms do.

[Steve arrives with Lance’s Beer. There is much happiness.]
Steve: My favorite talk so far was Rahul Santhanam’s [abstract] Reminded me of the good old days of complexity.

Lance: Let the guy give me beer and he thinks he can weasel his way into our typecast.

Bill: Lance, that’s how I got started in this business.

Lance: Rahul had some clever co-author, didn’t he?

Steve: No one important. Lance something?

Harry Buhrman: I like the GCT talk by Josh Grochow. [abstract]

Bill: In the future we’ll all have to learn GCT to get started in this field. I’m glad I’m living in the past. Lance, you paid me the highest compliment in my talk. You didn’t fall asleep and you even picked a fight with me.

Lance: Only because I had to stay awake to help the audience understand your confusing presentation.

Bill: It was only one slide.

Lance: It was only one fight.

Bill: I still feel as complimented as a bit that’s just been toggled .

Lance: I’m happy for you. Actually, it was not that bad a result. Now that’s my highest compliment.

Harry: Hey, this isn’t fair, we’ve haven’t heard all the talks yet.

[Both Harry and Steve are talking later tonight]

Lance: Life isn’t fair, get over it.

Bill: Let’s call it a day.

Lance: Watch my twitter feed later this week for a special musical complexity tribute.

Bill: I can’t wait.

Lance: So until next time, remember that in a complex world, best to keep it simple.

Matching Nobel Prizes

This week Bill and I have traveled to Germany for the Dagstuhl Seminar on Algebraic and Combinatorial Methods in Computational Complexity. Plenty of newly minted Nobel laureates here, winners of the Peace Prize last Friday. But this post celebrates today's winners of the Economics Prize, Al Roth and Lloyd Shapley for their work in matching theory that has made a difference in the real world.

In 1962, Shapley and David Gale created the first algorithm that finds stable marriages. David Gale would surely have shared this award had he not passed away in 2008. Nicole Immorlica's guest obit of Gale nicely describes this work and its applications including matching medical students with residencies.

Al Roth uses matching algorithms for a variety of projects, most notably creating large scale kidney exchanges, saving lives with algorithmic mechanism design. Doesn't get cooler than that.

Why Does College Cost So Much?

When John Hennessy gave his talk on MOOCs at the CRA Snowbird meeting he recommended the book Why Does College Cost So Much? by Robert Archibald and David Feldman, both economics professors at William and Mary. I've never seen a good answer to the title question so I read through the book. To overly simplify their main thesis: It's not that college has gotten more expensive, it's that most everything else has gotten cheaper. Technological advances in manufacturing and shipping have made greatly lessened the cost of goods, and the rate of inflation is calculated based on a basket of goods. So service industries, particularly those that require highly educated people and don't benefit directly from technology, look expensive in comparison. College costs closely map to medical and dental expenses, and closely followed broker expenses until technology made brokerages cheaper.

Archibald and Feldman even argue that there isn't a college affordability crisis for the majority of Americans: They are still better off than 30 years ago even if we take out college expenses. Hardly the doom and gloom scenario that Hennessey was portraying.

Their main point is that one cannot increase the number of students to faculty without decreasing the quality of education. That's where MOOCs come in, supposedly the solution to allow faculty to be far more efficient in the number of students they can teach without reducing quality. Might help control college costs but could harm research at top tier universities and many other universities might cease to exist.

Alas perception is reality and the public sees college expenses growing dramatically compared to the general cost of living and blames wasteful spending at universities. Curing this "disease" might kill the patient.

Theory Day. How to get the word out on this and other events?

Aravind asked me to post on this again (NOTE- registration-for-free deadline
is TOMMOROW!!!!!)

The University of Maryland at College park is having a Theory Day on Wed Oct 24! Come hear

1. Distinguished talks by Julia Chuzhoy and Venkataesan Guruswami!
   
2. Short talks (is that code for NOT distinguished?) by Bill Gasarch, MohammadTaghi Hajiaghayi, Jonathan Katz, Samir Khuller, David Mount, Elaine (Runting) Shi, and Aravind Srinivsans. (I never realized I was first alphabetically until now.)
   
3. Discussions in hallways for those that learn more that way!
   

For more info see the link above, but note one thing: Its FREE! NOTE: This is purposely after the NJ FOCS conference and is an easy Amtrak ride from NJ. I like theory days in general and often go to the NY theory days. They are free and only one day. I recommend going to any theory day that is an Amtrak Ride away. (Might depend on how long the trip is- There is a 13-hour Amtrak from Atlanta Georgia to Maryland, though I doubt I'll see Lance there.) I get a lot out of theory day as noted in this post about NY theory day. What are good ways to get the word out about events.

1. The major conferences and also the NY Theory Days have a long enough tradition that they don't need much advertising.
   
2. Email is not as useful as it used to be since we all get too much of it.
   
3. There IS a website for theory announcements here, and also one of our links, but more people need to post there and read there. A chicken and egg problem.
   
4. Twitter. No central authority. If Aravind had a twitter account (I doubt he does) then he could tweet to his followers, but that would not be that many people.
   
5. Any ideas?
   

Cruel XOR unusual Punishment

(This post was done with the help of Lane Hemaspaandra and John Purtilo.)

The 8th amendment of the US Constitution states

Excessive bail shall not be required, nor excessive fines imposed, nor cruel and unusual punishments inflicted.

There is an ambiguity here. Let C be cruel and U be unusual. They are saying NOT(C AND U) = NOT(C) OR NOT(U). Common sense would dictate that they meant NOT(C) AND NOT(U).

1. 
   (This article was emailed to me by Lane H. along with the idea for this post.) This article (see also this Wikipedia article) is an example where the CRUEL but NOT UNUSUAL argument seems to have been explicit. The case was about a MANDATORY life sentence in prison for possessing over 650 grams of cocaine, in Michigan. Is that a lot? (I never could figure out that Metric System.) In terms of numbers or getting high I really don't know if 650 grams is a lot, but legally its NOT A LOT--- the only other state that comes close to this kind of penalty is Alabama with a life-sentence for 6500 grams---that is not a typo. (See the Wikipedia articles section on White's criticism of Kennedy's argument.) I quote the syllabus of the decision which is not written by the members of the Supreme Court and is not part of the decision, but is rather prepared by the Office of the Clerk (of the Supreme Court)---who, one assumes, is pretty darned good at extracting the key points of the ruling, and so the syllabi are very useful.
   

   Severe, mandatory penalties may be cruel, but they are not unusual in the
   constitutional sense, having been employed in various forms throughout
   the Nation's history.
   

   Some past rulings HAVE indicated that a sentences that is out-of-proportion with the crime MAY be considered Cruel and Unusual. But, alas, unlike mathematics, definitions can change over time. (Well- in math that happens sometimes, but not often and usually not with dire consequences.)
   
2. One could argue that Capital Punishment is C but NOT(U). And indeed, the courts have often upheld it. Did they they use the argument that Capital punishment is C but NOT(U), hence it does not violate the 8th amendment? This article (emailed to be my Lane) makes that line of reasoning explicit and is against it.
   
3. If someone commits anti-Semitic vandalism and the courts decide that he or she is forced to read Anne Frank's Diary, that would be U but NOT(C). Not sure how they would enforce this- give a quiz? Are Cliff notes okay? What if the vandal saw the movie instead? Would this really work? (I honestly don't know.) Is this Hypothetical? In America YES. John found a case in Italy and I found a case in Germany). If this gets to be a common punishment for anti-Semitic crimes then it may no longer be unusual. I could find no other real cases where people convicted of crimes had, as part of their sentence, that they had to read something (though IANAL so there could be some I don't know about).
   
4. If an Occupy Wall Street guy vandalizes a Financial Institution's offices and is forced to read Atlas Shrugged that would be unusual. But is it cruel? (My opinion: YES) How about the Cliff notes? (My opinion: NO) Is this hypothetical? (My opinion: YES.)
   
5. What if a teenage girl was in Juvenile court for cutting off the hair of a 3-year old (against the 3-year old's will) and the Judge agreed to reduce the sentence if the teen's mother cut off the teen's pony tail in court. This would be considered unusual. But is it cruel? Is it hypothetical? No
   

It is most likely that the phrase Cruel and Unusual was not meant to be
broken down into its component parts.

So what Logic did the founders use?
Thomas Jefferson knew more math than any of the founding fathers. But alas,
he was off in France when the constitution was written.

Close to Genius

The MacArthur Foundation announced their 2012 Fellows, also know as the genius awards. Among the list two names of interest to my readers, Maria Chudnovsky and Daniel Spielman.

My long time readers first heard of Maria back in 2003 when I posted about a great talk she gave as a graduate student giving a polynomial-time algorithm to test for perfect graphs. That was just a start in her incredible career as a graph theorist.

Dan is a regular in the blog for the various awards he's won, most notably (before the MacArthur) for his Nevanlinna prize. I believe Dan is my first genius co-author, alas not one of the papers that causing him to win awards.

I've seen many cases where researchers get fantastic results early in their career and can never live up to the hype. Dan and Maria exceeded it. Congrats to both of them.

Quantum Workshop

I went to the QIS workshop on quantum computing which was on the College Park Campus. I went Thursday (reception- free food!) and Friday (free lunch!) but had to miss the Friday free dinner and the Saturday session.

1. Going to a conference that is ON your campus usually makes it FURTHER away for you. If I was from out of town I would have gotten a Hotel Room in the same hotel as the conference. As it was I walked from my office- a 45 minute walk It would have been shorter but it was a quantum random walk.
   
2. Scott Aaronson was there. We were talking about teaching class while being taped. He said that being taped changes what he does. I cleverly pointed out that the act of measuring Scott, changes Scott. He cleverly replied that the search for a NEW and FUNNY quantum joke has not ended yet.
   
3. Frank Gaitan gave a talk on using quantum annealing to find Ramsey Numbers. FINALLY a real application for Quantum Computing! (The downside- I was going to use Quantum Computers Find Ramsey Numbers! for an April Fools Day post.)
   
4. Umesh Vazarni's talk on CLASSICAL results proven using QUANTUM techniques was great. This notion seems to be for real. Its looking more and more like even if you don't like quantum you will have to learn it. A particular example of this is this paper
   Linear vs Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds by Fiorini, Massar, Pokutta, Tiwaray, de Wolf.
   
5. Yi-Kai Liu gave a talk on Quantum Information in Machine Learning and Cryptography. We discuss a small part of his talk, a result by Oded Regev. (Daniel Apon gave a full talk on this small part at the UMCP Complexity Seminar, his slides are here.) GAPSVP(γ) is the following problem: Given an n-dim lattice and a number d output YES if the shortest vector in L is ≤ d, and output NO if the shortest vector in L is > γ d (if it's neither we don't care what you output). This is NP-hard to solve exactly or within O(1) approx (though to be hard for evern poly approx) and it's a good problem for crypto to use. LWE is the Learning with Errors Problem. There is a quantum-reduction that shows that GAPSVP ≤ LWE, so if GAPSVP is hard then LWE is hard. So there are now three scenarios:
   
   1. Quantum computers are not built. Factoring is still hard classically. Crypto goes on as it is now (maybe not- there is a classical reduction from GapSVP to LWE, but for weaker parameters- so maybe you can base crypto on LWE).
      
   2. Quantum computers are not built. Factoring is easy classically. GAPSVP is hard. Do Crypto based on GAPSVP.
      
   3. Quantum computers are built. Factoring is now easy. GAPSVP is hard. Do Crypto based on LWE. THIS is what the result allows us to do!
      
   4. Quantum computers are built. Factoring is now easy. GAPSVP is easy. Now you are in trouble.
      
6. New word: Stoquastic. Not sure what it means.
   
7. Issac Chuang spoke about the difficulty of teaching quantum computing since the students have different backgrounds. He has devised (or helped devise) Online Tutoring systems for it that seem to be working very well. I didn't know that quantum computing was at the level to worry about how-to-teach-it. Then again, any course has these concerns, so it's good to see that he did something about it. (Even so, I doubt I'll invest a lot of time and effort into an online tutoring system for my Ramsey Theory course next spring.)
   
8. There were some talks on or touching on Quantum-Prog Languages, Quantum-CAD, Quantum-architecture. I suspect that if quantum computers are ever built we will find that some of the assumptions of this work were wrong; however, I also suspect that having people who have thought about these issues will be valuable.