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.

RaTLoCC (Ramsey Theory in...)

I was at RatLoCC last week which stands for Ramsey Theory in Logic, Combinatorics and Complexity. The idea was to bring in researchers for all three areas (actually its more than three) and have them learn about each others areas.

1. During Szemeredi's talk he said I am not an expert on Ramsey Theory. He meant to say I am not an expert on Ramsey Numbers, e.g., the current upper and lower bounds on R(5).
2. An anagram of Banach-Tarski is Banach-Tarski Banach-Tarski.
3. Bertinoro hosted both RaTLoCC and SUBLINEAR (a workshop on ... SUBLINEAR things) at the same time. We had some shared activities with them. They were a younger, hipper crowd. Ronitt Rubinfeld (who was there) told me they had LESS women than they thought they would have- only 4. We had MORE women then we thought we would have- 2 (we had 0 last time).
4. There were several blogs about the SUBLINEAR workshop: Day 1a Day 1b Day 2a Day 2b Day 3 Day 4a Day 4b
5. One measure of how much you get out of a workshop or conference is how many papers you are inspired to read when you get back home (or perhaps how many pages-of-papers or theorems, or some measure.) With that in mind, here is a list of some of the papers that inspired me. (Slides and abstracts are posted at the workshop's website.)
   1. Szemeredi talked on Arithmetic progressions in sumsets. Here is a sample theorem. Throughout A is a subset of {1,...,n} and n is large. A+A is the set of all sums of two elements of A. LA is A+A+...+A (L times). Sample theorem: For all C there exists c such that if |LA| > Cn then LA has a cn-AP (an arithmetic progression of length cn.) These theorems look HARD but it inspires me to read some papers on Alon's website on this topic, and also my own writeup of sum-product theorems (He used C and c in his talk- though some of them looked the same.)
   2. Noga Alon talked on List Coloring and Euclidean Ramsey Theory. A graph is L-List colorable if there is a way to assign each vertex L colors so that there IS a coloring of the graph where each vertex uses on of the colors assigned to it. Let G be the unit distance graph in the plane: vertices are points in the plane and two points are connected if they are distance one apart. This graph is known to be 7 colorable, known to NOT be 3-colorable. All else is open. Noga talked about his proof (co-author Kostochka) that G is NOT list-s-colorable for any s. The paper is on his website and I am INSPIRED to read it. (ADDED LATER- THE DEFINITION I GAVE ABOVE IS NOT CORRECT. SEE COMMENT BELOW.)
   3. Peter Cholak talked on Reverse Mathematics of Ramsey Theory. Reverse mathematics is a field where they have set up several axiom systems for mathematics (in a hierarchy) and, for MANY theorems of math, they know EXACTLY which system is needed. Infinite Ramsey Theory for PAIRS seems to be stubborn- it is not in any of the usual systems. (formally: RCA cannot prove it, but ACA is too much). It is provably DIFFERENT from Infinite Ramsey for TRIPLETS (which is equivalent to the theorem for 4-tuples, 5-tuples, etc, and for all of them ACA is exact.) My question: when I prove Ramsey for triples I do not feel the earth move or think MY GOODNESS- THAT STEP WAS NONCONSTRUCTIVE!!!! or anything else that is different from Ramsey for pairs. They told me that there IS a proof of Ramsey for pairs that, once you see it, you DO NOT know how to generalize to triples. I may try to look into this. I may not. The paper is at Peter Cholak's webpage and is titled On the strength of Ramsey's theorem for pairs. (co-authored by Jockusch and Slaman)
   4. David Conlon's talk Hypergraph Ramsey Numbers was about Ramsey's theorem for triples. For this case the upper bound is double-exp but the lower bound is single-exp. They made some progress on this, but the upper and lower bounds are still, pretty much, what they were. Still- proofs look very interesting. Progress here is unpredictable--- Conlon said that the problem could be solved next week or next month or not for one hundred years. Also, the proofs are clever- so Erdos COULD HAVE done them. (As opposed to results that use mathematics unknown to anyone in Math at the time.) I am INSPIRED to read this paper by Conlon, Fox, and Sudakov. The case of 3-hypergraph is interesting because, if the lower bound can be gotten up to double exp then for k-hypergraphs we will know that upper and lower bounds are roughly tower(k-1). (Uses the STEPPING UP Lemma.)
   5. Swastik Kopparty talked on The complexity of computing roots and residuosity in finite fields. Say you are in a ints mod p and you want to know whether x is a cube root or not by a constant depth circuit. This will take exp number of gates. Framework is the same as the Parity not in ACC_0 proof, but requires lots more math. MIGHT want to read it. MIGHT be too hard.
   6. Imre Leader gave an excellent talk on Euclidean Ramsey Theory. Here is the basic problem: Let S be a set of points in Rⁿ. IS it the case that, for all c there exists a finite set T in R^m. (m \ge n) such that, no matter how you c-color T there will be a CONGRUENT copy of S? The unit line has this property. If so then S is RAMSEY. It is known that if S is Ramsey then S lies on the surface of some (many dim) sphere. The Main conjecture is that the converse is true. NO says Imre! He has an alternative conjecture here. This paper I am INSPIRED to read.
   7. Jan-Christoph Schlage-Puchta (that is one person) gave an application of VDW's theorem to Completely Multiplicative Automatic Functions This one I NEED to read to put in my book on VDW's theorem. Its here
6. The best talks were those that really TOLD YOU WHAT THE PROBLEM WAS so that the no-specialist could at least here that and then TOLD YOU WHY THEY CARE (even if you don't care you should know why they care) and TOLD YOU SOMETHING ABOUT THE TECHNIQUES. Not all of the talks did this. Also, the best talks were on BLACKBOARD- it forces you to go slower. Not possible at STOC/FOCS etc since the audience is too big, but quite possible here. Only drawback- can't put blackboard talks on the web so easily (though you can if you videotape).
7. The youngest participant: James Pinkerton, my High School Student, gave his talk on Duplicator Spoiler Games that go on an ordinal number of moves. The talk was AWESOME! Before hand he was not scared. He said Whats the worst they can do? Throw red and blue tomatoes at me?
8. One of the people there wore a T-shirt that said Stand back, I'm doing SCIENCE! that had a picture (stick figure really) of a scientists with a test tube. He wore it two days in a row. I commented: Nonconstructive proof that you are a supernerd. Either (1) You wore the same T-shirt two days in a row, so you are a supernerd, OR (2) you have two copies of the same nerdy T-shirt, so you are a supernerd. Of course, in these surroundings, being called a nerd or a supernerd is not an insult.

75 Years of Computer Science

As Lipton and Felten note, today is the 75th anniversary of Turing's On Computable Numbers, With an Application to The Entscheidungsproblem, the seminal paper of seminal papers in computer science.

If you read any part of it, read Section 9, his justification of why the Turing Machine model captures computation, an argument that still resonates today.

No attempt has yet been made to show that the “computable” numbers include all numbers which would naturally be regarded as computable. All arguments which can be given are bound to be, fundamentally, appeals to intuition, and for this reason rather unsatisfactory mathematically. The real question at issue is “What are the possible processes which can be carried out in computing a number?”

The arguments which I shall use are of three kinds.

1. A direct appeal to intuition.
2. A proof of the equivalence of two definitions (in case the new definition has a greater intuitive appeal).
3. Giving examples of large classes of numbers which are computable.

Once it is granted that computable numbers are all “computable” several other propositions of the same character follow. In particular, it follows that, if there is a general process for determining whether a formula of the Hilbert function calculus is provable, then the determination can be carried out by a machine.

Cell Phones versus Drunk Driving

Most of you are familiar with the research that using a cell phone is just as dangerous as driving drunk.

Method: We used a high-fidelity driving simulator to compare the performance of cell phone drivers with drivers who were intoxicated from ethanol (i.e., blood alcohol concentration at 0.08% weight/volume). Results: When drivers were conversing on either a handheld or hands-free cell phone, their braking reactions were delayed and they were involved in more traffic accidents than when they were not conversing on a cell phone. By contrast, when drivers were intoxicated from ethanol they exhibited a more aggressive driving style, following closer to the vehicle immediately in front of them and applying more force while braking. Conclusion: When driving conditions and time on task were controlled for, the impairments associated with using a cell phone while driving can be as profound as those associated with driving while drunk

That and similar research has led to bans on hand-held (though usually not hands-free) cell phone use in many locations. Statistics are hard to come by but there are more alcohol-related accidents and many more alcohol-related deaths than those due to cell phones. Yet there are far more people talking on cell phones than driving drunk. This contradiction bugged me. What's going on?

Unlike using a cell phone, drunk driving is not a binary event. It's not that you are either drunk or you aren't. There are degrees based on the blood alcohol level. The real dangerous drivers are those way over the legal limit. Driving at the legal limit (0.08% in Illinois) isn't that dangerous or the limit would be lower.

When we hear that using cell phones are just as dangerous as driving drunk, we think, wow, cell phones are very dangerous. But our thoughts of the dangers of drunk driving is not at the level of drunkedness that are compared to cell phones.

Driving at the legal limit and on your cell phone are only mildly more dangerous than driving sober and distraction free. I'm not recommending that you drink or use your cell phones while you drive, you are certainly safer without doing so. But you should also be careful about reports about the dangers of activities and be sure the comparisons are correct. 

Is Computer Science Cool Again?

Back in 2005 I worried about loss of excitement about computer science among America's youth.

Today computers have become almost as commonplace as televisions and teens use them for a variety of tasks, including researching on the web, communication via email, instant messaging and blogging, and writing papers, all without an inkling of how to program. Computers have become a commodity and they don't see an additional value in knowing how and why they work any more than they need to know physics to drive their cars.

Yesterday IBM's David Ferrucci gave a talk at Northwestern on the challenges of creating Watson to play Jeopardy. The large lecture room was packed mostly with undergrads. Ferrucci didn't disappoint showing the challenges of Watson with lots of examples keeping the talk not too technical. Ferrucci will give a similar talk as an FCRC plenary speaker or you can watch a short version here.

My 12-year old daughter Molly came and enjoyed the talk and insisted on meeting Ferrucci afterwards just to tell him how cool Watson was.

The number of CS majors has grown dramatically in recent years at Northwestern and other universities. Bank of America runs ads on their ATMs that understands peoples checks ("How do they do that?") and Ford on how its Focus parks itself. And our local high school next year is teaching computer science again.

Håstad to receive the 2011 Gödel Prize

The 2011 Gödel Prize is awarded to Johan T. Håstad for his paper:

Some optimal inapproximability results, Journal of the ACM, 48: 798--859, 2001.

Håstad is the fourth person to win the prize twice (after Shafi Goldwasser, Mario Szegedy and Sanjeev Arora). He won the 1994 Gödel Prize for his switching lemma and tight bounds on parity for low-depth circuits.

The official citation:

This is a landmark paper in computational complexity, specifically, the study of approximation properties of NP-hard problems. It improves on the PCP Theorem (recognized in a previous prize in 2001) to give novel probabilistic verifiers that can check membership proofs for NP languages while reading very few bits in them — as little as 3 bits. The existence of such verifiers implies that existing approximation algorithms for several problems such as MAX-3SAT cannot be improved if P is different from NP. In other words, there is a "threshold" approximation ratio which is possible to achieve in polynomial time, but improving upon which is NP-hard. Before this paper such "optimal" inapproximability results seemed beyond reach. The Fourier analytic techniques introduced in this paper have been adapted in dozens of other works, and are now taught in graduate courses in computational complexity. They also directly influenced subsequent work, such as the formulation of the unique games conjecture for proving further optimal inapproximability results, and lower bounds for geometric embeddings of metric spaces.

On demand Publishing (guest post)

Cambridge Press (and others) offers PRINT-ON-DEMAND for some books. This is a guest post by Lauren Cowles from Cambridge Books about this, and then my comments on her comments, and then her comments on my comments. We stop there or else this could go on forever (OR we could make each block half the size of the prior block...)

LAUREN:

Print on demand is expanding rapidly all over the publishing industry. It's a way to keep books available if not forever at least much longer than they otherwise would be. This benefits people who want the books and the publishers who want to sell them.

The main factors are: Printing technology is now generally computer-driven, like everything else. There is no longer any need to set up film (or plates) to print from; many printing presses work from something that's essentially a fast and very high resolution laser printer. Therefore there is less economy of scale because there is much less in the way of set-up cost.

It is still cheaper to print several hundred books than to print them one at a time, but not nearly as much cheaper as you might think. So for many books there is now a tradeoff between the cost of the warehouse space and the unit cost. Also, of course, publishers are not spending money on books they might not sell. When sales drop below the point at which this tradeoff favors a conventional printing, we can often switch a book to being printed on demand simply by emailing the printer -- most of the printers we use now do both "conventional" printing and print on demand.

To get a print on demand book, all a customer has to do is order it in the normal way. The process is also so fast now that the customer normally has to wait only a few days more than if the book were in stock on the shelves.

BILL:

1. Will there be a time when there is NO cost diff between ordering one book and ordering in bulk? Will book companies only print on-demand?
2. Will Kindle and similar devices make print-on-demand a short-lived technology?
3. What does print-on-demand and kindle mean for the future of book publishers?
4. If these are cheap enough will they undercut the used-book market? If Kindle is the future will there no longer be such a think as a used book? (Molly Fortnow's daughter will ask Whats a used book mommy?.)
5. For academic books I am very happy that they will live on forever via either on-demand or kindle. Sometimes out-of-print math books are either impossible to find or are too expensive.
6. Will the notion of a rare book be obsolete?

LAUREN:

1. I doubt that the unit costs for print-on-demand will ever be cheaper than the unit costs for 500+ copies. But the PoD cost is low enough now that companies can make the choice for every book, and change that choice later in the book's lifetime. There already exist companies that only do print on demand (Lulu, for example).
2. Again, I doubt it.
3. Print on demand means we can keep things in print longer. What Kindle means is anybody's guess. Here in the publishing industry we are living in interesting times.
4. If fewer new books get printed, there may be a vogue for the old printed object... The used textbook market may be affected. I think the big textbook publishers have been trying for ages to find an electronic textbook model that will catch on, so that they can sell the electronic thing over and over at some similar-to-used-book price rather than sell the big expensive textbook once (effectively, directly into the used book market). I like to think people are keeping their Cambridge books so the used book question doesn't arise. (NOTE FROM BILL: I tell my students that they can buy ANY edition of the book for the course, they do not need to get the latest one. NOTE FROM BILL: Cambridge Press mostly does high level monographs which people are less likely to sell used.)
5. Cambridge Press has brought hundreds of books back into print now that we can afford to reprint them (eg Beck and Chen, Irregularities of Distribution).
6. In the sense of hard-to-find, yes. Google books has been scanning a lot of out-of-copyright books and making them available electronically. Cambridge U Press is doing something similar: we have been scanning classic books in the University Library and offering them as print-on-demand (eg Gibbs, Elementary Principles of Statistical Mechanics). The original of this from 1902 is still rare.