The Sputnik Moment

Earlier this month the New York Times had a story Computer Studies Made Cool, on Film and Now on Campus followed-up on a series of short essays on Computer Science's 'Sputnik Moment'. No doubt computer science is a hot major again, the number of CS majors at Northwestern has doubled over the past few years and I hear similar stories elsewhere. My daughter's high school will offer computer science for the first time in years. Big companies are using real computer science ideas from IBM's Watson to Netflix's recommender systems to nearly everything Google does. Obama talks robots at Carnegie-Mellon.

Mehran Sahami called this Computer Science's Sputnik Moment, evoking the phrase used by the president in his State of the Union Speech.

 Half a century ago, when the Soviets beat us into space with the launch of a satellite called Sputnik, we had no idea how we would beat them to the moon.  The science wasn’t even there yet.  NASA didn’t exist.  But after investing in better research and education, we didn’t just surpass the Soviets; we unleashed a wave of innovation that created new industries and millions of new jobs.

This is our generation’s Sputnik moment.  Two years ago, I said that we needed to reach a level of research and development we haven’t seen since the height of the Space Race.  And in a few weeks, I will be sending a budget to Congress that helps us meet that goal.  We’ll invest in biomedical research, information technology, and especially clean energy technology -– (applause) -- an investment that will strengthen our security, protect our planet, and create countless new jobs for our people.

The fate of that budget remains unclear in the current congress.  But there's an excitement for CS and science in general that we haven't seen since the 60's.

Computer Science seems to run in cycles, we build up excitement (the spread of personal computers in the early 80's, the Internet in the 90's and social networks and machine learning today) and soon after people see these as commodities and the excitement wanes. We need to not squander the current good will, find a way to keep CS exciting. The computer science story has a long way to go. Computer science needs to be a front office profession leading the way and not just in the back office keeping it going.

Math on FUTURAMA and LAW AND ORDER:CI

MATH ON TV

FUTURAMA mentions the Banach-Tarski Paradox! In the June 23, 2011 episode Professor Farnsworth invents a Banach-Tarski-Dupla-Shrinker which takes a blueprint of an object (like a sweater or Bender) and some matter and then produces two smaller but otherwise identical copies of the original. The real Banach Tarski Paradox takes one object and produces two of the exact same type. The writers might have felt that was just a little too weird. See here for a full description of the episode. The episode aired on thursday, and today, Tuesday, a full description is on Wikipedia. This surprised me (so fast!) but did not surprise my great nieces and nephews.

LAW AND ORDER: CRIMINAL INTENT had its last episode Sunday June 26, 2011, thus ending a rather long running show which was part of a rather long running (and still running) franchise. Here is the whole list: Law and Order (1990-2010, 456 episodes), Law and Order: Criminal Intent (2001-2011, 195 episodes), Law and Order: LA (2010-2011, 22 episodes), Law and Order: SVU (1999-2011, 272 episodes, and still going), Law and Order: Trial by Jury (2005-2006, 13 episodes), Law and Order: UK (2009-2011, 26 episodes, and still going). 456 episodes is HUGE! Check out this list of long running TV shows. The list is only updated once a year This surprised my great nieces and nephews (so slow!) but did not surprise me.

I recall three episode of Law and Order:Criminal Intent that mentioned math. I am sure there are more.

In the episode Bright Boy there was a school for gifted children in math that tried to get 10 year olds to work on the Riemann Hypothesis. It was not clear if they wanted them to solve it as children (which seems absurd) or as adults later in life (not absurd but a real long shot). The reason I find it absurd that a 10 year old could solve RH is that cleverness and brilliance is not enough- you have to actually have learned a great deal of math, perhaps too much for a 10 years old to have learned. Problems that need lots of KNOWLEDGE really can't be solved by bright 10 years olds or amateurs, no matter how brilliant they are. (See here for a post of Lipton's about of when amateurs helped solve math problems.) Getting kids interested in math by having them work on RH is the opposite of using Math competitions. Lance and I discussed math competitions as a way to interest kids in math here. Which is better? Even if you get bright pre-high school students working on problems, having them work on RH would just lead to frustration. Are there math programs that have student work on real open problems? How about phony open problems (the mentor knows the answer ahead of time). Some REU's do this for College students, but is there anything like this for High School Students?

The episode Inert Dwarf involved a brilliant physicist who, for medical reasons, was in a wheelchair (modeled vaguely after Stephen Hawking). One point of interest: he had a password that was based on hard physics and hence uncrackable. Gee, I thought that you just need to make sure your password is (1) not a word in any language (2) long enough, and (3) used Upper Case (easy for ME), lower case, numbers, and punctuation symbols. Unless it was some sort of quantum system (the episode did not indicate this) I can't see how hard physics can make a password uncrackable.

In some episode this season (I forget which one) Goren (the detective) was given the following riddle by his psychologist: There are two doors and two guards. One of the doors leads to heave, the other to hell. One of the guards always tells the truth and one always lies. You get to ask one guard one question and then you must pick a door. Goren is supposed to some sort of genius who also knows a great deal of stuff so I'm surprised he didn't know it. In the last episode of the entire series, To the boy in the blue knit cap, he answers it correctly. I think that was supposed to be symbolic or meaningful or something, but I didn't see why. (Bad writing? I'm being dense?) (ADDED LATER- ACTUALLY GOREN ASKED THE PSYCHOLOGIST THE QUESTION WHICH MAKES MORE SENSE IN TERMS OF WHO-KNOWS-WHAT.)

Bright Boy and Inert Dwarf had the same problem that many TV shows have: If the real world fact do not make the plot work, the writers change the real world facts. Numb3rs did this with Math quite a lot.

FCRC 2011. Part 2 of... probably 2.

(A workshop on Coding, Complexity and Sparsity will be held at Ann Arbor, August 1-4, 2011. See this website.)

More thoughts on FCRC.

1. Russell Impagliazzo is one of the Luddites (spellcheck made me use a capital L) in the field (I'm another, and I know of one more person in Complexity who could be called a Luddite) who famously uses transparencies at talks. BUT, he has entered the 1990's- he gave a talk on PowerPoint (or something like it). (Spellcheck made me use two capital P's). I asked him why he made the change. The ability to SCAN IN his old transparencies was one of the keys. (Of course, he probably could have done that 10 years ago...) The talk was on his world view. I don't mean how he feels about the debt ceiling or Libya or Global Warm ning or the problems in FILL IN ANY COUNTRY THAT HAS PROBLEMS. I mean his worlds:
   1. Algorithmica: P=NP
   2. Algorithmica: NP ⊆ BQP. This was in a talk he gave at a workshop. Its in a link below but was not in his CCC talk.
   3. Heristica: P ≠ NP but NP problems are tractable on average for any samplable distribution.
   4. Pessiland: There are NP problems hard an average AND there are no one-way functions.
   5. Minicrypt: P ≠ NP, one-way functions exist, but public key crypt is impossible.
   6. Cryptomania: P ≠ NP, public key crypto is possible.
   For the CONTENT of his talk see Lance's blog entry. Blogs on his world are here and here. There was a workshop in 2009 on the worlds. You can actually see Russell talk about it, with transparencies, as a link from this page Russell's paper on the worlds was hard for me to find since its title is A personal view of Average Case Complexity which you can find on his web page. A POLL on which of Russell's works we live in would be interesting, but I leave that for someone else to do.
2. Les Valiant made the cover of CACM! I hope that eases the pain of no longer being the best theorist who had not won a Turing award.
3. Alan Borodin was the only one at STOC who had been to the first STOC (1969). I asked him if, at the time, he thought there would be a STOC 2011. He said that as a grad student at his first conference he thought more of it as being HIS first conference than STOCs first conference.
4. Several of my lunches were with people NOT going to STOC or CCC. A bunch of PLDI grad students asked me what he hot area in Theory was. I told them (1) Quantum is still strong, which surprised me, and (2) Algorithmic Game Theory seems hot now. Any other candidates for a short answer to this question if asked? Be prepared with an answer before the next FCRC.
5. I heard that one of the logistic problems was that different conferences gave out different stuff (bags, pens, paperweights. Paperweights?). I also heard some sniping How come that conference got so much better pens than we got?.
6. Jin Yi Cai gave a great talk at CCC about dichotomy for #CSP. Certain counting problems are in P and other ones are #CSP complete. Cai has managed to classify exactly which are which. I asked him about the CSP problem- is there any hope of a dichotomy theorem there. He said This talk is on Counting CSP. I asked him How Narrow are you?. He challenged me to read a 300 page paper in the field before accusing him of being narrow. Over lunch he gave me a better answer: Counting problems are hard in general so they have to be rather special to be in P, so classifying is doable. By contrast, CSP problems can be easy so its much harder to tell which are which.
7. The only ones at CCC that were at the first CCC were probably Fortnow, Allender, Gasarch, Selman, Homer. The founders of the conference were Book, Hartmanis, Mahaney, Selman, and Young. Selman is the only one who is still doing theory. (Book and Mahaney are deceased, Hartmanis and Young are retired.)
8. I don't bring a laptop to conference (I don't have one); however, I borrowed Marius Zimand laptop to catch up on some websites during one of the breaks. Then a talk came that I wanted to see and I could not pull myself away from the laptop. It can be addictive. I will never do that again. Other distractions such as doing math on paper I can break away from, but web surfing was hard to break away from. What are your experiences with this?

Blog Redesign

We redesigned the blog to use the newest Blogger features. This lets me not have to maintain the 2002 html code we had before and lets us have some new features like adding comments directly on the post page.

We, of course, kept the signature background color.

Creating an Email System at Cornell

Email celebrates its fortieth anniversary so let me tell the story of my job for three summers, and part-time during the academic year, while an undergrad at Cornell University: Creating an email system from scratch.

In my sophomore year (1982) I took an computer structure course. I had a heavy set of final exams and papers so I did the final program for this course early and turned it in the last day of class to the instructor, Steve Worona. In that class you could scale assignments and tests from 0.75 to 1.5 to make them count more or less. When I turned it in, Worona asked me why, if I'm turning it in a week early, did I scale it at 0.75? "You never give me A+'s on the programs and I didn't want to lower my grade."

That was perhaps my most obnoxious moment but it got me noticed and Worona, who worked for computer services, offered me a programming job. We would create a new email system for Cornell. Cornell had an email system written in some scripting language, slow and clunky. We wouldn't use any fancy high-level language, we would code directly in IBM 370 assembly language. We would do it all ourselves, user interface, database for storing messages, interactions with SMTP servers, etc to maximize efficiency. No small task which is why it took me nearly three years.

IBM Assembly language was quite bloated with instructions. There was a command called "Edit and Mark" that went through a range data making modifications based on some other data. This was a single assembly language instruction. We used to joke that there was a single instruction to do your taxes.

Cornell at the time was a gateway between BITNET ("Because It's Time NETwork", connecting about 30 universities in US and Europe) and a fledgling ARPANET, the precursor to the Internet. BITNET worked with files, ARPANET one line at a time so there was a special file-based Batch SMTP to transmit email between the two. The fun I had working this all out.

As a test bed, my email system was used in only one building, Day Hall, which held the university administration: President, Provost etc. Great pressure to make sure there were no bugs.

One day a company that helps get people green cards sent an email to everyone on BITNET. My first piece of spam.

As a side project I helped write an ARPANET interface into CUINFO, an early electronic information system at Cornell. That was pretty simple, we just used the Telnet interface into a different port. This is basically what HTTP does now. I could have invented the Web!

In my senior year I told Steve Worona that I was planning to go to graduate school in theoretical computer science.

"You really want to spend your life shaving log n factors off algorithms?"

"Yes I do." (But I never did, since I went into computational complexity)

"Well the world just lost a great programmer."

As soon as I left Cornell my email system was scrapped for a commercial product. C'est la vie!

I am conducting a NEW POLL on P vs NP

In 2002 I did a poll that appeared as SIGACT News Complexity Theory Column 36 on what people thought of P vs NP. See here.

That article is now linked to on Wikipedia and (much to my surprise) has come to be the AUTHORITY on what people were thinking then.

TEN years have passed! It is time to take the pulse of the community again. Hence I will ONCE AGAIN (!) be conducting a poll to appear in a SIGACT News Complexity Column.

SO- I would like you to email gasarch@cs.umd.edu (in LaTeX or plaintext) the answers to the questions below. (Comments to the blog will not be counted as answering the poll.) I would like to get this poll written this summer, so I will give a deadline of October 31, 2011. (I may extend this if I do not have enough responses.)

1. Do you think P=NP or not? You may give other answers as well.
2. When do you think it will be resolved?
3. What kinds of techniques do you think will be used?
4. Will the problem still be relevant given advances in algorithms and in SAT Solvers?
5. Feel free to comment on anything else: Graph Isomorphism, Factoring, Derandomization, Quantum computers, and/or your own favorite problem.
6. Do I have your permission to print your response? I will do this for some people--- how many depends on how many answer the poll.
7. What is your highest degree in and where is it from? This information will be used for statistics only.

Theory Jobs 2011

The computer science job market never comes to a complete close. CI Fellows are still being decided, Oxford is just starting its search for an algorithms professor. But many jobs have settled so it is time for our annual list of who is going where. Many of the strong theory groups have hired this year, surely spurred on the by the competition for the new Simons Institute but still we have way too many theoretical computer scientists doing multiple postdocs or taking industrial or financial jobs.

For optimal crowdsourcing I created a Google spreadsheet that everyone can edit and for all to view. Do not add or modify the sheet unless you are sure a job has been offered and accepted. It may take some time for the embedded sheet below to update to the latest changes.

FCRC 2011. Part I of... maybe I, maybe more.

I do not log on at conferences so I came back to 400 emails. Exactly 400- not sure how I managed that. TODAY I am posting about a few things from FCRC, I may post more next week as I remember them.

1. CCC finally no longer has proceedings. Most conferences at FCRC did not have proceedings. ISCA, the International Symposiusm on Computer Architecture, still has proceedings. I asked someone from ISCA why they still have proceedings. They gave an answer which boils down to That's the way we've always done it. Also, ISCA has MONEY so they don't need to save money as well.
2. The best student paper award at STOC went to Analyzing Network Coding Gossip made Easy by Bernard Haeupler. Great Talk!
3. The best paper award went to Electrical Flows, Laplacian Systems, and Faster Approximation of Network Flows in Undirected Graphs Electrical Flows, Laplacian Systems, and Faster Approximation of Network Flows in Undirected Graphs by It also might be a contender for longest title. A better title might have been Electrical Flows and Networks Flows. Great talk. Looks like a paper I can actually read and understand. Network flows is a well studied problem- one slide had over 30 references on it. (ADDED LATER: A helpful commenter pointed out that The Best Paper award was actually shared by the FLOWS paper and also by Subexpontential lower bounds for randomized pivoting rules for the simplex algorithm by Friedmann, Dueholm, Hansen, and Zwick. This seems to be unknown to thiswebsite.) (ADDED EVEN LATER- The page I just pointed to now DOES know about the two awards and has been updated.)
4. I skipped the talk on The Computational Complexity of Linear Optics by Aaronson and Arkhipov since I saw some version of it a while back. My mistake- talks I see twice I actually understand, and I heard it was an excellent talk. Going to Scott's webpage to make this post I spotted a paper on using Linear optics to prove the PERM is #P complete. THATS the paper I really want to read! Serendipity is alive and well.
5. Proof Complexity means two different things: (1) proving that theorem X NEEDED to use Axioms Y or had to be nonconstructive of level Z, and (2) proving that certain formulas need exponential number of steps to prove they are not satisfiable. This talk tried to use a theorem (the Paris Harrington Ramsey Theory) that is not provable in Peano Arithmetic requires a long proof in some systems. They end up saying that if a version of Paris Harrington (that CAN be proven in PA) has a short proof then Pigeon hole principle has a short proof. This is rather odd- the only thing they can prove DIRECTLY requires long proofs is PHP, so everything reduces to it. The talk is here, the paper is here, for a writeup of the version of Large Ramsey they were talking about see here
6. Ryan Williams won the Best Paper award at CCC for this paper. Lance did an excellent blog on the result a while back here. (NOTE- the link to the paper seems to be down now. Hopefully it will come back up soon.)
   1. On his website it has next to the paper Will receive Best Paper award. Did he put that there when he submitted ASSUMING that he would win it? That doesn't sound right. Did he put it there when he found out he would win it? That doesn't sound right either-- being notified that you won it is the same as receiving it.
   2. I would like to think that he was inspired by my April Fools Day post of 2011 which said we should all go out and PROVE things instead of whining about barriers and oracles. Actually its the other way around- Ryan inspired the post when, at some DAGSTUHL, we were all saying what we can't prove and he said When do you think we will separate NL from PSPACE? I fell for it and said Not for a while at which point he reminded me that its already known. That inspired the post.
   3. Whenever a new result appears the question arises Did it use new techniques or a clever combination of old techniques. Or more egocentric Could I have proven that? For example, if Wiles proof of FLT is really the only way to do it then Gauss could not have done it. Ryan's proof looks like a really really clever combination of older results. This is NOT to downgrade it. And NO, I could not have done it. A better question: will it lead to MORE results? IS P vs NP just around the corner? No.
7. CCC 2012 is in Portugal. CCC 2013 is at Stanford co-located with STOC. CCC 2014 MIGHT be in Koyoto Japan. Is that a good idea? If there exists N people who CAN go if its in Japan and NOT otherwise but M people who normally go but now can't then if N and M are roughly the same or even if N is a bit bigger, than I think we should do it. Not sure what the real values of N and M are.
8. Some grad students I talked to think that CCC and/or FCRC should have an after-conference Survey Form to fill out about the conference so that they can improve things for next time. I agree!

New Complexity Vidcasts

The newly renamed Computational Complexity Channel features two new vidcasts Bill and I hosted last Thursday from San Jose.

Bill's Enigma

Interview with Ryan Williams

Talks I Missed

The Complexity conference comes to a close today and I head back to Chicago. I tend to go to few talks, preferring hallway conversations, but occasionally I hear about a few great talks that in retrospect I wish I attended.

The first STOC talk, The Power of Simple Tabulation Hashing by Pătraşcu and Thorup. Simple hashing scheme that takes a random function of pieces of an input and XORs them together. Surprisingly this simple scheme is close to looking like a fully random hash function for a variety of purposes.

The last of Thursday's Complexity talks, Property Testing Lower Bounds via Communication Complexity by Blais, Brody and Matulef. An easy reduction from communication complexity to property testing gives a large number of new lower bounds for property testing based on known bounds for communication complexity.

Another FCRC comes to an end. Next year in New York (STOC) and Porto (Complexity).

An Update on Impagliazzo's Worlds

Russell Impagliazzo gave a talk at Complexity about his five worlds. We didn't know whether Heuristica and Algorithmica were different, i.e., whether if NP is easy on average then its also easy in the worst case. Russell gave an oracle relative to which where NP is easy on average but P ≠ NP. There are now relativized separations of all his worlds.

Russell announced that it was his first talk ever using a computer instead of transparencies. We gave a round of applause welcoming him to 1998. His talk consisted of some PowerPoint slides with black text on a generic white background and some very cute hand-drawn cartoons that he scanned in to his talk. Someone asked for animation. Maybe next decade.

In less than an hour new Stanford professor Ryan Williams gives the Complexity talk on his great result that NEXP not in ACC⁰. With no surprise, Ryan won the Complexity best paper award, the second-highest honor his paper has received.

The Longest Day

Tuesday at FCRC.

7 AM: A grad student at Northwestern administers my final exam at 9 AM Chicago time. He has my mobile number just in case but luckily I never get a call.

7:30: Saw Sampath Kannan in lobby. Says he has a sister who is married to a finance professor at Northwestern. I say, wow that's a coincidence, Ravi Kannan's sister also has a husband who is a finance professor at Northwestern. Then it hits me.

8:30: First STOC best paper winner talk by Madry gives better algorithm for approximating undirected max flow.

8:55: Skip second best paper talk to go across the hall to see Northwestern student Nima Haghpanah give his EC talk.

9:20: Back at STOC for the best student paper by Bernhard Haeupler. My favorite FCRC talk so far, a simple method for spreading "gossip" through a network with an analysis that uses a clever union bound that cannot possibly give tight results, yet it does.

9:43: Email saying 10 exams are being FedEx'd to me for grading. There are 12 people registered for the course.

11:30: Ravi Kannan's Knuth Prize lecture. Working in high dimensions can often do wonders for algorithms.

12:30: Electronic Commerce exec committee lunch to talk about location of EC 2012.

2:04: Email from student who thought the final was on Wednesday.

4:00: Find out the SIGACT Treasure can't make it to San Jose. Sends me material for the business meeting.

4:25: My only FCRC talk, an EC paper with Michele Budinich, an Italian student who couldn't make it to FCRC.

6:00: EC Business Meeting. Starts late so they barely get through introductions when I have to leave for

6:30: SIGACT Exec Comm dinner

8:15: Stop in at Complexity Reception

8:30: Stop in at EC Reception

9:00: STOC Business Meeting where I serve as emcee. I put all the slides here. Some highlights

• A little over 300 registrants at STOC
• Accepted 84 out of 304
• Poster session considered highly successful
• Give out Knuth Prize (Ravi Kannan) and Gödel Prize (Johan Hastad)
• FOCS 2011 in Palm Springs October 23-25. 
• ITCS 2012, now sponsored by SIGACT, January 8-10. Submission deadline August 7.
• SODA 2012 in Kyoto, January 17-19. Submission deadline July 5.
• STOC 2012 in New York, May 19-22.
• STOC 2013 will be in Palo Alto.
• Not much love for Salil Vadhan's proposal to require on-line archive version of paper on submission.

10:30: Meeting Ends. Talk with Paul Beame about timing of next Knuth Prize (FOCS 2012) and off to bed.

Another busy day today as STOC, EC and Complexity all have talks at the same time. But at least my jobs are done.

A Valiant Weekend

In my role as SIGACT chair, I got to attend the ACM Awards Banquet held at the beginning of FCRC in San Jose. I shared a table with Mitzenmacher who posted on the banquet earlier. Theory did well among the award winners but none so notably as the Turing Award, the "Nobel Prize of Computer Science", awarded to Leslie Valiant. Valiant, in his acceptance speech, gave a wonderful shout out to the STOC conference for helping him shape his research, or at least the STOC conferences back in the 70's when the theory community were still figuring out the right questions and models. A nice contrast to the ACM Press Release that focused on the connections to AI.

Last night, Valiant gave the Turing Award lecture at FCRC. His main thesis is that evolution is just an example of computational learning and we need to understand the computational process that led to the development of us in a relatively short period of time. I heard a similar talk he gave at Berkeley caused some consternation among the biologists who don't want to give anyone fodder that evolution might not be possible because it is too complex.

My take: Evolution has a significant random element and we need to condition that randomness on the fact that we exist. The biologists and computer scientists on Mars aren't asking these same questions about why they never came to be.

Partioning Students

One last Molly post for the end of the school year. Tomorrow is her birthday and I enter that moment I have been dreading for the past thirteen years: Two teenage daughters.

Molly's 7th Grade Science teacher wanted to break her class into groups of three to work on a particular project. Each person in the class was asked to list three people they wanted to work with and one person they didn't. The teacher would partition the class so everyone wanted to work with someone else in their group and the person they didn't want to work with was not in their group.

The next day the teacher she thought the partitioning should be easy but took her many hours. One student said she should just ask a computer to find the partitioning. Molly said she needed the right algorithm. When Molly told me about it that night and asked if I could help her figure out the algorithm. I said the problem was likely "NP-complete" (since it is a variation of Exact Cover) and would have to search all the 190 million different partitions of her class of 18 into groups of 3. OK, I probably said this to get out of thinking about an algorithm but maybe Molly got just a little more understanding of P versus NP.

Bill and I are at FCRC next week. Hope to see you there.