Random thoughts on the election

Neither Lance and I have commented much on the Prez election.
I only found one post from 2012 that mentioned Romney:
Romney vs Aaronson.
A few mentioned Obama but not with regard to the election.
I give you some Random thoughts on the election before its over.
They are nonpartisan unless they are not.

1. I polled the Sophmore discrete math class (secret ballot) and got the following: of the 99 students in the class (1) 64 for Obama, (2) 17 for Romney, (3) 8 for Gary Johnson (libertarian), (4) 2 for Jill Stein (Green). Those were the only ones on the ballot; however, there were some write-ins: (5) 2 for Ron Paul, (6) 1 each for Newt Gingrich, John the Baptist, Mickey Mouse, Gumby, and two names I did not recognize but may have been the students themselves. You know what they say: As goes discrete math, so goes the nation. Hence Obama now has it in the bag.
   
2. I predicted it would be Romney vs Obama on Feb 15, 2012. I also predicted that Obama would win. I never wavered from that prediction, so you can't call me a flip-flopper. You can read it here. The first part (Obama vs Romney) has already come true; we will see if the second one does.
   
3. Assuming Obama wins I have a bet on the Republican nominee in 2016: I have bet Lance Fortnow, Chris Umans, and Amol Despande (DB guy in my dept) that it will be Paul Ryan.
   (ADDED LATER- I misunderstood Amol- he wants to bet WITH me, that Ryan will win,
   with the odds I got.) If I win I get $1.00, if they win they get 30 cents. I have a bet with Mike Barron (a friend of mine not a theorist--- yes I have non-theorists friends), who is more of a risk-taker, where if I win I get $10.00 and if he wins he gets $3.00. Are these good odds? I ask this nonrhetorically.
   
   1. Why Ryan? 1972 is the beginning of the modern political era. That's when Prez candidates had to compete in primaries to win the nomination. (Humphrey got the nomination in 1968 without entering a single primary, then the McGovern Commission changed the rules so that a lot more primaries were included. And, the man who understood the rules, McGovern, got the nomination in 1972.) Since 1972 the Republicans have almost always nominated a KNOWN person, someone you heard of four years earlier. Not including incumbents here is the list:
      
      1. 1980 Reagan. Known- Had run in 1976.
         
      2. 1988 Bush Sr. Known- Was VP under Reagan.
         
      3. 1996 Dole. Known- Had run with Ford as VP, had run for Prez before.
         
      4. 2000 Bush Jr. Unknown- One can argue he was known via his dad, but I'll just say Unknown.
         
      5. 2008 McCain. Known- Had run before in 2000.
         
      6. 2012 Romney. Known- Had run before in 2008.
         
      By contrast the Dems have sometimes nominated someone you had not heard of. Here is their record:
      1. 1976 Carter. An Unknown Former Gov or Georgia.
         
      2. 1984 Mondale. Known, Former VP.
         
      3. 1988 Dukakis. An Unknown Gov of Mass.
         
      4. 1992 Clinton. An Unknown Gov of Arkansas.
         
      5. 2000 Gore. Known. Was VP.
         
      6. 2004 Kerry. An Unknown Senator.
         
      7. 2008 Obama. An Unknown Senator.
         
      (One could debate how unknown some of these were.) Note that whenever the Dems nominated a known person they lost- perhaps a cautionary note to those who want Biden or H. Clinton in 2016, and an encouraging note to Andrew Cuomo, current gov of NY. (If you say whose that? you've proven my point.) But ANYWAY, the Republicans have ALMOST ALWAYS given it to a KNOWN person. None of the people who ran for the nomination in 2012 seem plausible to get the nomination in 2016, though The Daily Show is doing a segment on the fictional Cain Presidency. Some sort-of-known people who didn't run in 2012 but may in 2016: Chris Christie (Gov of NJ), Jeb Bush (Gov of Florida), Tim Pawlenty (Gov of Minnesota), Mitch Daniels (Gov of Indiana), Marco Rubio (Senator from Florida), Bobby Jindal (Gov of Louisiana) . The last two are more known for being talked about as Prez of V Prez Candidate then for anything they've actually done. I grant that any of these people are possible. However, they are not quite as well known as Ryan. Also, I predict that if Romney loses it will be blamed on we were not true to our principles and they will go further rightwing with Ryan.
   2. Why it might not be Ryan: The above argument sounds convincing but the problem with predictions in politics (and elsewhere) is that, to quote a friend in Machine Learning, Trends hold until they don't. Anything could happen! Things may change drastically! As an example see this XKCD.
      
4. Another prediction, though harder to quantify. When Gore, Kerry, and McCain lost they or people around them said things like I let my handlers handle me too much- if I had run as myself I would have won. I predict that Romney will think the same thing. I doubt he'll say it.
   
5. There is an issue on the Maryland Ballot that involves Game Theory and Gaming. Roughly speaking the issue is should we allow more gambling in our state. PRO: People are going to adjacent states to gamble and we should get that money. CON: Gambling is a regressive tax and bad for the economy in the long run. The more states have gambling (or build baseball stadiums or give businesses who move there tax breaks) the more other states have to go along to compete. A classic Prisoners Dilemma--- except that West Virginia and Delaware have already defected so we have no choice. Or do we? There is a rumor that the anti-gambling adds in Maryland are being paid for by the West Virginia Casinos. The anti-gambling ads are not anti-gambling, they are just against this bill- they claim that the money won't really go to education for example. I admire the honesty--- if a West VA casino had an add in MD saying how bad Gambling was morally that would look rather odd. Even so, Should I vote FOR gambling just to spite the out-of-state casinos running adds in my state? Should I vote FOR it since the ads against it are not giving MY arguments against it? Should I vote FOR IT and tell people I voted against it?
   
6. There is a marriage-equality referendum on the ballot- Question 6. There has been almost no ads or talk about it. Why? One speculation--- the people against it know they will be on the wrong side of history, and the people for it don't quite know how to sell it. Its ahead in the polls so maybe they don't want to rock the boat.
   
7. If you ask a pro-Obama pundit who will win he might say Obama because people know Romney is a liar. If you ask a pro-Romney pundit will win he might say
   Romney because Obama has not fixed the economy and Mitt can. Either may use poll data as window dressing, but they tell you what they want to happen rather than what an honest scientific study will show. Nate Silver, a scientific pollster, says in his book The signal and the noise: Why so many predictions fail--- but some don't that pundits are right about half the time. Not surprising.
   
8. George McGovern died recently at the age of 90. The 1972 prez election, McGovern vs Nixon, was the first Prez campaign I paid attention to. I passed out McGovern pamphlets in my precinct of Brooklyn and McGovern DID win that Precinct. I regard that as a Moral Victory.
   

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.
   

Things a Complexity Theorist Should Do At Least Once

A few weeks ago, Suresh wrote a post Things a TCSer should have done at least once with the caveat

This list is necessarily algorithms-biased. I doubt you'll need many of these if you're doing (say) structural complexity. 

Basically begging a response. So here is what every structural complexity theorists should have done.

• Define a new complexity class that has some reason for being.
• To keep balance in the world, you should also collapse two other complexity classes. 
• While you are at it, separate two complexity classes that weren't separable before. 
• Create a new relativized world. Extra points if in this work you collapse two complexity classes while separating two others. 
• Use Kolmogorov complexity, information theory or the probabilistic method as a proof technique. They are really all the same technique in disguise.
• Use the sunflower lemma, or the Local Lovasz lemma, or some other weird probabilistic or combinatorial lemma just for the fun of it.
• Invoke VC dimension to solve a problem. I should have at least one in common with Suresh and Sauer's lemma is sometimes useful in complexity. 
• Have a theorem that starts "Assuming the extended Riemann hypothesis..."
• Give a "simpler" proof of a nasty theorem. 
• [Advice given by Noam Nisan many moons ago] Try to settle P v NP. In both ways. Only by really trying and failing can you understand why the easy stuff doesn't work. 

A new kind of Spam

(In this post I quote attempted posts to the blog.
I transcribe them as they are, so if you see a missing period
or awkward language, its not me (this time) its them.)

We moderate comments but do so very lightly.
There is no hard and fast rules but roughly speaking
we block comments that are BOTH offensive AND off-topic.
There may be exceptions- like if its on topic but REALLY REALLY offensive
and adds nothing to the discussion.
There may more benign exceptions- like if I post a question and will block the
answers so that when I reveal the answer the next day its more dramatic.
Of if someone posts information that is not public yet.
In these case we hope they try to post non-anonymously so we can email them
and tell them why they were blocked. There are other isolated cases as well.
All of these are very rare.

Recent attempted comments do not fall into these rules and we had to
decide on them. The following was an attempted comment on my post
about
STOC 2012-Workshops and honored talks

Hi there STOC 2012- workshop and honors talks Loved every second! Great views on that!
That actually breaks the mold! Great thinking!

This comment is NEITHER offensive NOR off-topic.Its a bit odd- I can't tell if
the Great view is of my post or of the talks I was writing about.
It does sound awkward. Why is that? IT WAS GENERATED BY A SPAMBOT!!!
How do I know this? Because if you click on the author you are directed to a site thatsells you paints for your living room.Hence we block such posts.

So, they think the readers of our blog are into interior decorating.
I am sure that some are, I don't think our readers are a particularly good market for this. Technology is good enough to find our blogs and try to use spambots on them,but not good enough (or there is no incentive) to figure out which blogs are worthtargeting.This is part of a bigger problem I blogged about
herewhere I noted that technology is good enough to know that I am a book review editor for SIGACT NEWS but notgood enough (or there is no incentive) to figure out that I only review comp sci and math books, and not
books on (say) politics.

A borderline case: an attempted comment on the blog
A natural function with very odd properties was

Awesome logic. You truly have some expert skills and enhanced my knowledge on Cantor Set Construction Agreements.

This one did not link to any product so it might be legit, except thatit is awkward sounding and the same person tried to submit,as a comment to Six Questions a about natural and unnatural mathematical objects

This truly enhanced my skills. very helpful Job Proposal.

Clearly spam, though I'm not sure why since there is no link to a product.

These posts are trying to pass a Turing Test- but so far they are not succeeding.

Sometimes they only positive comments I get are from spambots. Oh well.

Poset Games are PSPACE-complete

Consider the following game on a poset, each player takes turns picking an element x of a finite poset and removes all y ≥ x. First one to empty the poset wins. I posted last March about a high school student, Adam Kalinich, who showed how to flip the winner of a poset game.

Finding the winner of a poset game is in PSPACE by searching the game tree. A corollary of Adam's work showed that poset games were hard for Boolean formula leaving a huge gap in the complexity of finding the winner.

Daniel Grier, an undergrad at the University of South Carolina, has settled the problem and shows that determining the winner of a poset game is PSPACE-complete. His reduction is ridiculously simple (though not obvious) and the proof is not that complicated either.

Grier starts from Node Kayles which is a game on an undirected graph where each player takes turns removing a vertex and all its neighbors. Whomever empties the graph first wins. Thomas Schaefer showed the PSPACE-completeness of Node Kayles back in 1978.

Grier's reduction from Node Kayles to posets is very simple: Let G be the graph. Have one element in the poset for each vertex of G, all incomparable. For each edge e=(u,v) we add two more elements, one above the vertex elements corresponding to u and v, and one below every vertex element other than u and v. That's the whole construction.

Grier shows that if G has an odd number of edges and no immediate win for the first player then the first player wins the Node Kayles game if and only if the first player wins the corresponding poset game.

You can read more details in Grier's short paper. It's really neat seeing high school students and undergrads solving interesting open problems. We need more problems like poset games.

Theory Conferences Galore

Early registration for the FOCS conference in New Jersey is September 27th. There is some travel support available for students and postdocs, deadline is this Friday the 21st.

STOC and Complexity will be co-located in Palo Alto in early June. STOC CFP (deadline November 2), Complexity CFP (deadline November 30).

SODA comes back to the US and New Orleans January 6-8. Accepted Papers.

Imagining Imaginary Probabilities

In the year 4000BC my great-great-...-great grandmother tried to solve (in today's terms) the equation

x² + 2x + 2 = 0

She discovered that if it had a solution then there would be a number a such that a²=-1. Since there clearly was no such number, the equation had not solution. She missed her chance to (depending on your viewpoint) discover or invent complex numbers.

Fast Forward 6012 years.

In the year 2012 I wondered: is there a probability p such that if you flip a coin that has prob(H)=p twice the prob that you get HT is 1/2? This leads to

p(1-p)=1/2

If you solve this you get p=(1+i)/2. Hence there is no such coin. WAIT A MINUTE! I don't want to miss the chance that my great...great grandmother missed! In the real world you can't have a coin with prob(H) = (1+i)/2. But is there some meaning to this?

More generally, for any 0 ≤ d ≤ 1 there is a p ∈ C (the complex numbers) such that ``prob(HT)=d.'' The oddest case (IMHO) was to take d=1. You then get that if a coin has prob(H)=(1+\sqrt(-3))/2 then prob(HT)=1. Does that mean it always happens? No since prob(TH)=1. Do the probs of HH, HT, TH, TT add up to 1? Yes they do since some are negative.

Is there an interpretation or use for this? I know that quantum mechanics uses stuff like this. Could examples like this be good for education? Are there non-quantum examples of the uses of this thatcould be taught in a discrete math course?

Max Flow

A couple of weeks ago Suresh tweeted the following result of James Orlin

Max flows in O(nm) time or better. jorlin.scripts.mit.edu/Max_flows_in_O…
— Suresh Venkat (@geomblog) August 31, 2012

I'm thinking, wow, max flow is one of the major standard algorithms problems, and O(nm)  time (n = number of vertices, m = number of edges) seems like a great clean bound. But there hasn't been much chatter about this result beyond Suresh's tweet.

Reading Orlin's paper gives some clues. The previous best bound due to King, Rao and Tarjan has a running time of O(nm log_{m/(n log n)}n) = O(nm log n) just a logarithm off from O(nm). Orlin doesn't directly give an O(nm) algorithm, his takes time O(nm+m^31/16log²n). It's the minimum of the running times of King-Rao-Tarjan and Orlin's algorithms that yields O(nm). Nor is O(nm) tight, Orlin also gives an algorithm with a running time of O(n²/log n) when m=O(n).

I don't mean to knock Orlin's work, he makes real progress on a classical algorithmic problem. But somehow I think of O(nm) as a magical bound when it is really just another bound. I'm just fooled by simplicity.

Some quantum Stuff

Two quantum announcements (emailed to me by Umesh Vazirani, and producedhere almost exactly) and then some thoughts of mine quantum computing.

Announcement one: The NSF has a new initiative to try to address the lack of tenured faculty (particularly in computer science departments) involved in quantum computation research.  CISE-MPS Interdisciplinary Faculty Program in Quantum Information

The initiative provides a paid sabbatical year to interested tenured faculty to visit a strong quantum computing group, so that can reposition their research interests. The rationale behind the solicitation is to increase the number of tenured researchers in quantum computation, but also to break through the "quantum skepticism" in faculty hiring decisions in those departments where there are no faculty actively involved in quantum computing research.

Announcement two: In support of this program, Carl Williams (a physicist working in Quantum Information who put together the US Vision for Quantum Information Science for the Office of the President) and Umesh have put together a workshop where interested individuals can learn about the initiative, the field and make contacts with people from the major quantum computing centers: see here.

The initiative comes at a particularly opportune moment for researchers in complexity theory, given the increasing relevance of quantum techniques in complexity theory --- the 2-4 norm paper of Barak, et al (SDPs, Lasserre), exponential lower bounds for TSP polytope via quantum communication complexity arguments (See Drucker and de Wolf  paper Quantum proofs for classical theorems for several apps of Q to Complexity, and see
here for the TSP polytope result)
quantum Hamiltonian complexity as a generalization of CSPs, lattice-based cryptography whose security is based on quantum arguments, etc.

MY COMMENTS: Umesh gives as a reason quantum is important its uses in other parts of complexity theory. While that is certainly good there are other intellectual reasons why Quantum is worth studying.

1. Factoring is in Quantum P! There are MANY problems (maybe 10) where Quantum seemsto be faster than classical.  I wouldn't really want to push this point sincequantum computer aren't build yet. More generally, if one claims a field is validfor real practical value, those arguments may become less believable over time.
   
2. Quantum computing can be used to simulate quantum systems- I think this was one of the original motivations.
   
3. Quantum computing is valuable for a better understanding of Physics.
   This was first told to be my Fred Green (A Physics PhD who went into computer science)and I made it the subject ofthis blog entry.
   I like his quote so much that I will quote it here
   

   
   Learning quantum computing helped me understand quantum mechanicsbetter. As a physicist I never thought about measurement theoryor entanglement, which were foundational issues, irrelevantto what was doing. In quantum computing, we reason about thesethings all the time.

   
   Over the years others have told me similar things.

Side note: The word Quantum is mostly misused in popular culture. Quantum Leap meant a big leapwhen actually quantum means small. The James Bond movie Quantum of Solace used it correctlybut was an awful movie. Oh well.

The Time of Research

Among the many conference/journal discussions, one systems person said the reason they don't publish in journals is that their work is very dependent on current technology. A few years in the future the technology will change and this research is no long relevant. The best systems research develop ideas that transcends technology, but much research in systems have a limited lifespan of relevancy.

In theory, if you prove a theorem that theorem will be true forever. In fact that theorem was always true, we just didn't know it. So it is important to have refereed long-term archival write ups of these results. A theorem could be supplanted by another result or get less interesting over time but it always remains true.  Theory results transcend technology, though most theory result have a zero lifespan of relevancy.

Theory Day at UMCP Oct 24

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 Srinivsan.  (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!

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

(ADDED LATER AT THE REQUEST OF THE ORGANIZER:
Theory day at UMCP is intentionally after the NJ Focs and is an easy amtrak
away from NJ. The stop is New Carolton)

Should we learn from the Masters or from the Pupils?

The following is a paraphrase of a comment at the end of the Suggested Readings section of Spivak's calculus book:

Abel remarked that he attributed his profound knowledge of mathematics to the fact that he read the masters, rather than the pupils.

Are you better off reading the Masters or the pupils?  This of course depends on the masters and the pupil and other factors.

1. I have heard that Godel's original papers (even when translated) are well written and show a profound understanding of the subject and why its important.
   
2. However, we now have a better understanding of what Godel did and better ways to express it.
   
3. The Masters may include the motivation which may be lost in later papers.
   
4. Often the first proof of anything is ugly or odd and later proofs really clean it up.
   
5. Often the first proof of anything uses only basic concept- later abstractions may hide the heart of the proof.
   
6. As a practical matter sometimes the early papers are not available (thanks to paywalls or obscurity) or in a language you do not read.
   
7. If Lance and I ever do a book-of-blog-posts I will clean up some of the spelling, make some of the arguments more clear (perhaps indicate where I am being sarcastic in cases where it was not understood), improve the writing. This will make it better than the blog but less authentic.

Here are examples where the Masters papers may not be worth reading:

1. Recursion theory in the early 1960's had several infinite injury arguments. I have heard that they were known to work only because the lemmas and proofs worked out.  Only after Bob Soare's excellent article on the topic were they really understood. For 0''' priority arguments it is also true that the early papers are not the ones to read.
   
2. Example (and the real motivation for this post). I have tried to read Ramsey's original article. I knew that his goal was a problem in logic, and I wanted to know what that problem was. I had a hard time reading the paper.  (I did  my own writeup.) Why was his version so hard to read?  (1) He never uses the words coloring or graph or hypergraph. He doesn't mention that if you have six people at a party either three of them know each other or three of them don't know each other. Perhaps he didn't go to many parties.  (2) He uses odd terms at time.  (3) His paper is rather abstract. If he had just proven a simple case then it would be obvious how to proceed to his abstract case.  This is true for both his combinatorial theorem--- he only proves (what we would call) the hypergraph version, and also the Logic theorem.
   
3. The Cliff notes for Atlas Shrugged are far better than the book. Shorter too.  They are online for free here which makes sense since Ayn Rand was known for her altruism.

SO- what do you think? Examples of cases where the Master is better to read?
Examples of cases where the Pupil (or more generally later summaries, surveys, expositions) is better to read?

The Net or the Jet

I spent the first half of my life in the jet age but not in the Internet age. I could fly anywhere in the world but the fastest way to get a research paper to another scientist was to bring the paper on the plane with me.

One could imagine technological innovation going the other way around where we had a functioning Internet but no air travel. Maybe we would have done a much better job creating virtual meetings and conferences.

Suppose you had to choose a world to live in:

1. Jets but no 'net. We know what this world looked like.
2. Net but no jets. We can only imagine.

Which one would you choose?

[This question came from a discussion with Paul Royal, a Georgia Tech research scientist in Information Security. We chose different answers.]

Neil Armstrong, Ray Bradbury: The future is not what we thought it would be

Neil Armstrong died on August 25, 2012.  He was the first man to walk on the moon.  (Since they always say this I wonder if Women walked on the moon earlier.) Ray Bradbury  died on June 5, 2012, though on this (and perhaps other) blogs with was overshadowed by death of Mihai Patrascu on the same day.

When man landed on the moon I thought that this would be a common thing- that we'd goto the moon about once a year. In the end only 12 people walked on the moon and we stopped going in 1972.  See here for details.

Why didn't we go more often? Maybe there wasn't much to see- you see one moonrock you've seen them all. Are unmanned flights much better in terms of science-for-the-money? I suspect yes.  Also, one reason America put men on the moon was to beat the Russians to it.  Once we already did that, the point was made, so no reason to go again.

If we went now it would cost much less. So perhaps we should have waited for the technology to catch up and go later for much cheaper.  That's not quite right- one reason we have some of the technology is that we went then. But in some areas- computers in particular- certainly we would have still made progress without going to the moon.  On the other hand going to the moon when we did was quite inspiring to some people.  (Are you one of those people?)

Ray Bradbury's classic Farenheit 451  was about censorship- the government had firemen who burned books. Books made of paper. I suspect that within 10 years e-books will be the standard (some exceptions- Art books, maybe some Math books).  Will that make censorship easier or harder? The Arab Spring was caused partially because the government could not control social media. However, in China the government is pretty good at blocking access to the Web. But still, some gets through.  So to rephrase the question- does current technology make censorship easier or harder?  I don't have an answer to this question- but I invite your intelligent commentary.

Ray Bradbury himself has said that the book was also about people choosing a shallow culture (e.g., TV over books). Modern technology has been a mixed bag for this.  Some TV shows will one day (or even now) be seen as classics (e.g., The Simpsons) while others are of course going to be seen as vapid, shallow, and not worth much (e.g., Madmen).

Knuth Prize

Leonid Levin will receive the Knuth Prize, and give the corresponding lecture, at FOCS this year. The Knuth Prize is jointly given by ACM SIGACT and the IEEE TC-MFCS for outstanding contributions to theoretical computer science.

Levin easily deserves the award alone for his amazing two-page 1971 paper, actually two major research lines

• An independent discovery of NP-completeness and
• Universal search

Today we call the seminal NP-completeness result for Satisfiability the Cook-Levin theorem.

Levin did so much more, from the "right" definition for average-case hardness to (with Hastad, Impagliazzo and Luby) producing pseudorandom generators from any one-way function.

Congrats to Leonid!

Ten Years of the Complexity Blog

On August 22, 2002 I wrote the following immortal words to start this blog

This is my complexity web log. I'll be giving random thoughts about computational complexity and about mathematics and computer science in general.

Ten years and over two thousand posts later this blog keeps going.

Computational Complexity has come a long way since 2002. In post two I talked about the then new result showing that Primes are in P. Since then we've seen Reingold's log-space algorithm for undirected connectivity, Dinur's "simpler" proof of the PCP theorems, new circuit lower bounds and great new algorithms. Alas the P versus NP problem is still open.

Thanks to all of you for reading and commenting on the blog. It's your support that has keeps us going for the the last ten years and many more years to come.

Fellow blogger Abie Flaxman named Top Innovator!

(Guest post from William Heisel, Assistant Director for External Relations, Institute for Health Metrics and Evaluation, University of Washington, 2301 5th Avenue, Suite 600,Seattle, WA 98121)

Abraham (Abie) Flaxman who writes the Healthy Algorithms blog
(which is on Complexity Blogs' Blog Roll) has been named one of the world's top young innovator by MIT.  This is a sign that algorithms are finally getting a little respect in the global health and technology worlds.

In global health  the rock stars are the vaccines, new toilets, and bed nets. Health measurement is considered something for bean counters whose pasty skin never sees the blistering Sub-Saharan African sun. But what about the tech junkies? They must see the value in crunching all those numbers to do the world some good? Not so much. Techies get excited about apps and gadgets and new ways to monetize web hits.

Finally, Technology Review, MIT's tech industry Bible, is naming a health measurement pioneer (who happens to work at the Instutite for Health Metrics and Evaluation (IHME) IHME) to its list of the world's top young technology pioneers.  Here is the official press release:

For the first time, a prestigious technical innovation honor from the Massachusetts Institute of Technology (MIT) will go to an expert in health measurement: Abraham Flaxman, an Assistant Professor of Global Health at the Institute for Health Metrics and Evaluation (IHME) at the University of Washington (UW).

Since 1999, MIT's Technology Review has honored the world's top innovators under the age of 35 (TR35), in fields such as biotechnology, software, and energy. Until this year, the TR35 judges have not named an innovator in health measurement. Dr. Flaxman was selected from more than 250 nominations by a panel of expert judges and the editorial staff of Technology Review.  Past winners include Facebook founder Mark Zuckerberg and Google co-founders Sergey Brin and Larry Page.

Abie's technical innovations in the field of global health have been game changing in our ability to measure health and health interventions, IHME Director Dr. Christopher Murray said. He has - and continues to be - at the forefront of pioneering methods that improve our ability to measure health outcomes and the effectiveness of interventions that address the world's greatest health challenges.

Nowhere is this more important than in the upcoming Global Burden of Disease (GBD) 2010 Study. Dr. Flaxman is the youngest member of the core team for the ambitious study that aims to provide the most comprehensive assessment to date of the burden from death and disability for more than 300 diseases, risk factors and injuries. Dr. Flaxman advanced a new way of disease modeling that allows researchers to combine all of the world's data on prevalence incidence, remission, and mortality and produce consistent estimates of the way diseases progress through the population, as a function of age, time, sex, and geography. When the GBD study is published, it will give governments and health program funders the best picture yet of how the world has advanced or fallen behind in efforts to improve population health.  We are able to understand what is truly causing the greatest amount of mortality and disability in the world because of technical advancements that can be traced back to Abie scribbling on a white board in  his office, said Dr. Mohsen Naghavi, Associate Professor of Global Health at IHME and one of the lead researchers on the GBD project.

Dr. Flaxman also has made significant advancements in verbal autopsy methods for gathering health data in low-resource settings. His machine learning algorithm for computer-certified verbal autopsy takes the results of a health interview of relatives about a recently deceased person and automatically determines the cause of death. He also created a stock-and-flow model for tracking the distribution of insecticide-treated bed nets to prevent malaria. The results are updated annually and included in the World Health Organization's World Malaria Report.  The advancements Dr. Flaxman and colleagues have made in data-driven data quality audits (D3QA) were recently recognized at the Symposium on Computing for Development. Their publication on the development of the D3QA tool won on the best-paper award. The tool can be used to ensure that health data and other data gathered from household surveys are accurate. It is currently being used in research aimed at estimating mortality from war-related causes in Iraq.

Dr. Flaxman has accomplished all of this in just four years. He was on track to join the legions of computer scientists who staff technology giants such as Microsoft and Amazon. While working at Microsoft Research in 2008, he applied for an IHME Post-Graduate Fellowship. His extraordinary work as a Post-Graduate Fellow propelled him to being hired as a UW faculty member.

The world is not lacking in health data, and yet certain basic information has never been quantified, Dr. Flaxman said. I realized four years ago that I could use computational algorithms to solve some of these measurement challenges in global health. And I am incredibly honored to have been recognized by the TR35 judges for this work. Dr. Flaxman will discuss his work alongside other TR35 honorees at the EmTech MIT 2012 conference at the MIT Media Lab in Cambridge, October 24-26. All the TR35 winners for 2012 will be featured in the Sept/Oct issue of Technology Review

The Institute for Health Metrics and Evaluation (IHME) is an independent global health research center at the University of Washington that provides rigorous and comparable measurement of the world's most important health problems and evaluates the strategies used to address them. IHME makes this information freely available so that policymakers have the evidence they need to make informed decisions about how to allocate resources to best improve population health.

For more information about IHME, please visit: here.  Technology Review, Inc., is an independent media company owned by MIT It publishes Technology Review magazine, the world's longest-running technology magazine (established 1899).  Additional information about TR35 winners and judges is available here For more information about EmTech MIT 2012, please visit: here.

Is the Turing Test Still Interesting?

Besides the Turing machine, Alan Turing also developed what we now call the Turing Test in Turing's seminal 1950 AI paper "Computational Machinery and Intelligence". Turing describes his imitation game and says if a judge cannot distinguish between communicating with a computer versus a human than this is an indication of that a computer "thinks".

It's not clear exactly when a computer will pass the Turing Test but with systems like Watson and Siri we are getting very close. One can imagine that if we run the right machine learning algorithms on large data sets like Facebook chats or text messages, we can create a system that would fool most people. But would it really be intelligent?

Think about how Google translate works. There is no understanding of the meaning of the words in either language, just a statistical approach to develop a function that maps one language into another. Is this method really intelligence, are Google's computers "thinking"? Not really.

In a couple of years it will be clear that computers easily pass the Turing test. It will be another milestone, like beating humans at Chess and Jeopardy. The computers won't be any more intelligent by passing the test but they will be more useful. And I'll take useful over intelligent any day.

Book Review Column (a bit late)

I try to post my book review column when it comes out but I am behind on that. This is the one that came out a few months ago.  The column is here though I have removed the list of books I want reviewed since it is out of date. The current list of books I need reviewed is here.  Advice for reviewers is here.  The LaTeX template for reviews is here.

The books reviewed in the column are:

1. A Concise Introduction to Data Compression by David Salomon.  This book covers different aspects of data communications with a main focus on source coding, more commonly known as data compression.  We can view source coding as lossless compression, where the goal is to find a bijective function that when fed a bitstream, also known as a message, outputs a shorter bitstream.
   
2. Parallel Algorithms by  Henri Casanova, Arnaud Legrand, and Yves Robert.  This book provides the reader with an advanced introduction into the principles of Parallel computing.  The book is targeted at advanced readers -- graduate students and post-graduate researchers with a strong computational background -- and represents a good resource both in support of a graduate course in parallel algorithms, and for self-guided learning.
   
3. Polynomia And Related Realms by Dan Kalman.  This book is about polynomials. Topics include Horners rule, root finding (e.g., the cubic equation) and max-min problems. There is also some history in the book so you'll know where the ideas come from.  The MAA awarded this book a Beckenback Prize at the January meetings.  Details are posted here
   
4. Biscuits of Number Theory Edited by  Arthur T. Benjamin and Ezra Brown.  The authors themselves give the best description of the book: an assortment of articles and notes on number theory, where each item is not too big, easily digested, and makes you feel all warm and fuzzy when you're through.
   
5. Combinatorial Geometry and Its Algorithmic Applications: The Alcal\'a Lectures by Janos Pach and Micha Sharir.  Combinatorial Geometry is the study of points, lines, and planes.  This material often has algorithmic applications; however, unlike Computational Geometry, this is not the original motivation. This book explores the aspects of combinatorial geometry that have applications to algorithms.
   
6. Handbook of Large-Scale Random Networks Edited by Bela Bollobas, Robert Kozma and Deszo Miklos.  Networks can often be modeled as a random graph.  The research here is truly interdisciplinary.  This handbook is an outcome of a U.S.-Hungarian workshop on complex networks held at the R\'{e}nyi Istitute in Budapest in 2006.  According to its editors, its purpose  is to provide a significant update and extension beyond the materials presented in the ''Handbook of Graphs and Networks published in 2003 by Wiley
   
7. Algorithms and Theory of Computation Handbook Edited by : Mikhail J. Atallah and Marina Blanton.  This is a pair of volumes that cover many topics of interest to TCS research.  Volume I is mostly algorithms and Volume II has some real applications.
   
8. Primality testing and integer factorization in public key cryptography by Song Y. Yan.  This book covers number theory, some of which is quite advanced, and how it interacts with modern cryptography.
   
9. Process Algebra: Equational Theories of Communicating Processes by J. C. M. Baeten, T. Basten, and M. A. Reniers.  Process algebra is a method for specifying and verifying distributed and parallel systems that uses logic and universal algebra.  This book deals mostly with using Process Algebras for communicating processes.
   
10. Insider Threats in Cyber Security Edited by Probst, Hunker, Gollman, and Bishop.  This book seeks to educate the reader about the various aspects of insider threat and attempt to define/explain the problem (e.g., types of insiders, the nature of the problem and types of misuse), and ways in which end users and businesses can seek to mitigate some of these risks.  Other topics include fraud detection and insider threat mitigation technologies. Several challenges from both practitioner and research perspectives are discussed.

Another Algorithmic Market Failure

In 2009, Matt Cushman, Managing Director at Knight Equity Markets, gave a seminar at Northwestern on "High Frequency Trading". Here is the abstract:

High frequency trading has emerged over the past decade as a critical component of modern electronic financial markets. It provides liquidity, efficiency and stability to the global equities, foreign exchange, futures and other electronic marketplaces. By some accounts, two-thirds of US equity shares traded are done by high frequency systems. Yet, misconceptions abound in the popular media today concerning high frequency trading's impact and value to the broader economy.

We will discuss the value of high frequency trading, and some of the problems (both quantitative and technological) that must be solved to operate a successful high frequency system.

Much of the talk focused on how Knight put its servers close to those of the NYSE so it could be first in line for trades. I failed to see the societal value. Say at the airport if someone cuts in front of the security line, they get considerable extra value but it will be cancelled out by the lost time of everyone behind him.

The company, now called Knight Capital, tried out a new algorithm last Friday and lost $440 million buying when it should have sold.

I cry no tears for Knight but such losses can have a disastrous effect on the stability financial markets. One solution is to have the government or some other agency verify code before traders can use it on the markets. But code verification is practically difficult and theoretically impossible.

I would prefer a tiny transaction tax on every trade, negligible for all but high-frequency traders. Computation has made the market nearly frictionless, time to but some friction back in.

My take on the Olympics

Thoughts about the Olympics

1. If you are rooting for your country, would you rather they get (say) 18 medals: 6 Gold, 6 Silver, 6 Bronze, or 17 medals: 10 Gold, 4 Silver, 3 Bronze?  More generally, when is (g,s,b) better than (g',s',b') Some schemes:
   
   
   
   1. The commentators and the websites seem to use g+s+b. They say things like
      American is leading the Medal Count without breaking it down.  Given that the margins-of-victory are often rather small, and all of the athletes who finish in the top 3 (often even in the top 20) are quite good, I think that just g+s+b is good.
      
   2. If you want to value gold medals more than a scheme like 3a+2b+c makes sense.  One problem- the weights 3,2,1 are arbitrary. What would a criteria be for good weights?
      
   3. It may be a complicated function. For example (g,s,b) is better than (g',s',b') if g ≥ g'+4 OR (g ≥ g'-3 AND g+s+b ≥ g'+s'+b').
      
   4. You may want to allow for a partial order--- that is, some triples are incomparable.
   
   
2. Swimming or running: Often the top X people are 0.5 seconds apart and all close to or better than the world or Olympic record.  I would give them all medals. This is not some wimpy self-esteem crap--- if the athletes are that close together, and close to breaking records, they really are all excellent and you really can't say whose better. A possible scheme:
   
   
   
   1. If you tie or beat a world record you get a Gold Medal. (Might even allow if you are within X of a world record for some X.)
      
   2. If nobody has beaten or tied a world record and you tie or beat an Olympic record then you get a Gold Medal.  If someone else has beaten or tied a world record then you get a Silver Medal.  (I may allow some leeway in both cases.)
      
   3. The top person behind all of those people gets the bronze Medal.
   
   
3. Or we could give more medals: Gold, Silver, Bronze, Zinc, Aluminum, maybe more.
   
4. In Women's Gymnastics these women do spectacular things but if they land badly TAKE OFF X POINTS! Somehow that doesn't seem right.
   
5. In most events Women and Men compete separately.
   
   
   
   1. Track and Swimming: Since these are timed we can say without apology that the men are better, so its best if they don't compete head-to-head. However, if a women wanted to compete in the men's event she should be allowed to (Are they now? I doubt it.) I don't think this has come up. 
   2. Gymnastics. Here its NOT that either gender is better, its just that they do different things.  The very thought of a guy on the uneven parallel bars terrifies me.  The thought of anyone doing backflips on a 4-inch wide beam also terrifies me.
      
   3. Equestrian- from what I could tell from the Yahoo Schedule Website men and women compete equally here.
      
   4. Archery and Shooting are seperated by Gender. For Archery this might make sense- some strength is required.  For Shooting this makes no sense to me. I asked a guy who knows about shooting and he told me that many non-Olympic shooting sports are not seperated by gender.  So why are the Olympic Shooting contests seperated by gender? My guess is that its the same reason COLT allows PC members to submit and CCC does not: because that's how we've always done it.
   
   
6. Game theorist needed: The rules for Badminton were set up so that it was in China's interest to throw a game (see here).  In this case I think it should be fine for a team to forfeit rather than play badly on purpose. More important- the rules need changing.  The Blog Turing's invisible Hand discussed this here.
   
7. What sport do you most want to see in the Olympics? I would say Chess Boxing or Skeet Surfing. Both make more sense then the Olympic sport of Modern Pentathlon which combines pistol shooting, fencing, freestyle swimming, show jumping, and a 3 km cross country run.

MOOCs

I haven't posted in about a month. A combination of traveling, vacation, moving to Atlanta and getting started as chair. I appreciate why Michael Mitzenmacher stopped blogging as he became department head. I'll try to post once a week but no promises.

Last week I attended the CRA Snowbird meeting, a biennial meeting of CS chairs and other leaders in the field. The big topic this year: Massively Open Online Courses or MOOCs. Coursera just a couple weeks ago had their big announcement with their line-up of universities that will produce courses including Georgia Tech.

John Hennessey, president of Stanford, gave the CRA keynote address arguing that MOOCs will save universities. He puts the untenable costs of universities at personnel costs (faculty salaries) are making colleges unaffordable (not sure I fully agree). He argued that MOOCs will help teach courses more effectively. The hidden subtext: fewer professors and probably fewer universities, or as someone joked, we'll all be branch campuses of Stanford.


As pointed out by a few at the meeting there is nothing essentially computer science about MOOCs. But it's hard to ignore the CS influence: The Stanford courses that started the new MOOC era were in computer science, Coursera and Udacity are led by computer scientists, as are the MOOC centers at Stanford, MIT, Georgia Tech and many other schools. With great influence comes great responsibility so let's be sure to do it right.


About the only thing people could agree with is that the we are in the very early stage of MOOCs produced by major universities and nobody is sure where we are going. MOOCs may completely change higher education in America and around the world. Or they won't.