The revolution will be DVRed

(There are TWO theory day events in NY this semester: Thu Nov 11. and Fri Nov 12.)

BILL: Will you be going to the RALLY TO RESTORE SANITY AND/OR FEAR? (See also here.) It will be the event that defines this generation!!!! Just look at all of these pictures that will be taken there! Here are some pictures by Evan Golub who went, took pictures, then went home early to actually watch some of it. And here is a picture that is more suited to the readers of this blog.

DONNA: I'll DVR it.

Is this the wave of the future?

1. Even though watching a sports event on TV gives a better view and reasonably priced food (as opposed to the stadium which gives a terrible view and has overpriced food-like substances) most people say that being AT the game has a certain je ne sais quoi. At least people who think they know French say that. Will technology get SO good that being at home is preferred? Give the viewer the ability to pick what parts of the field he wants to see? Give him the ability to rewind in real time (already can via DVR)? 3-D? (not for a while). They might pay us to go to the game since an empty stadium looks bad for TV.
2. Museums: Why go to the Louvre when you can do a virtual reality tour of it which saves you the cost of a trip to France? I think this is possible with today's technology. If not, then certainly soon. There already is a partial virtual tour.
3. The rally was really crowded and I couldn't see much. Even so, being there had a certain I know not what which made it worth going. However, I'm glad I DVRed it so I can see what really happened. When I tell my great nieces that I was there at the dawn of a new age it will be partially fiction since I'll tell her of what I saw on DVR. Or I'll just show her the recording. You can also currently see it here.
4. Movie Theaters are facing a problem with people waiting for the DVD to come out rather than go to the theater. For families the economics are insane: buying the movie on DVD (and thus OWNING it) costs less than taking the family to see it once. COUNTERPOINTS: (1) Some people want to get out of the house. (2) Lance told me that I really should see AVATAR in a theater.
5. With conference talks online will people still go to conferences? (This was already discussed here but it fits today's theme also.)

Will technology make it easier and easier to stay home? I think yes. When that happens you may have some surprises- some Rally has far less people than anticipated because people worry it will be too crowded, but then for the next Rally people think it won't be that crowded so it gets more people than anticipated. Rather than count how many people were actually there you might calculate some weighted sum of how many were there, downloaded it, DVRed it, sign up on the Facebook page for it, etc.

By Any Other Name Would Be Just As Hard

In 1973 Donald Knuth searched for a name for the hardest problems in NP. Steve Cook didn't give a name in his paper and Karp called them P-complete. Knuth suggested three names "Herculean", "Formidable" and "Arduous". He sent out a ballot to people in the theory community and also allowed write-in votes.

The results he put in a SIGACT News Article, a fascinating and hilarious read. Of course Knuth's suggestions didn't fly and he got many quite inventive counter-proposals. My favorite: Hard-Ass Problems (Hard As satisfiability).

The winning solution came from a group at Bell Labs (likely including one of their new hires David Johnson), which you readers should all know as NP-hard and NP-complete. These names did have the advantage that it could generalize to other notions of hardness (like PSPACE-complete).

Knuth muses at the end

NP-hard problems hits lots of people, and that's why I began searching for a special term. In other words, I don't consider it a major goal to invent descriptive terminology for every conceivably interesting question of the type considered here; the major goal is to have a good term to use for the masses, in the one case which experience shows is almost omnipresent. To say NP-hard actually smacks of being a little too technical for a mass audience, but it's not so bad as to be unusable. 

The importance of the P versus NP problems has reached well beyond the theory community despite its name but I wish Knuth had been more successful in finding a descriptive term. P, NP, NP-hard and NP-complete are technical names that tend to isolate us and confuse others.

Advice on getting connecting to the community (guest post by Daniel Apon)

(Guest Post by Daniel Apon.)

As a follow up to the last post on Do Conferences Build Community? I offer some advice for people to get connected to the community.

1. Be Confident (And Smile!). It's absolutely important to give a positive first impression when introducing yourself to someone. Making eye contact, smiling, and speaking clearly go a long way toward making yourself an inviting person to have a conversation with. On other hand, one of the best ways to guarantee an awkward social experience is to act creepy; avoid that at all costs. And most importantly, meet as many people as you can!
2. Great Researchers Are People Too! Sure, the person you're talking to could have a history of landmark publications dating back before you even know was NP-completeness was, but don't forget that everyone you're meeting is a human being (really). Be respectful of course, but remember that they're probably in a similar situation to you -- meeting new people during a coffee break!
3. In the words of the immortal Fonz: Be Cool. One of the biggest turn-offs will be giving the impression that you want something from them. Go ahead and throw those types of ideas away immediately. If you're interested in the same things, conversation will flow naturally. Don't try to force anything; just let it happen.

(Comment from Bill G: The same advice applies to meeting people in bars, though you probably won't be discussing Fourier transforms over finite fields until your third drink.)

Do conference build community? (joint post)

(Joint Post by Daniel Apon and Bill Gasarch. Does doing joint posts build community?)

In GASARCH's post on Will there be a 50th CCC He mentioned that conferences help to build community. One of the comments challenged that. Daniel Apon is very new to the community and William GASARCH is very old to the community, so we decided to do a joint post on the topic: Do Conferences Help Build the Community?

1. The talks do not build community. The coffee hours and meals should. Do they?
2. Having people with similar interests all in the same place should build community. Does it?
3. Does size matter? CCC is only about 100 people so they can all sort-of know each other. MATHFEST has over 1000 so I never saw the same person twice.
4. I've heard the complaint that older established professors do not bother to talk to younger people in the field. This is bogus in its generality: it varies tremendously from person to person. Also, if an older professor ignores you it might not be that he thinks he is better than you, it could just be that he has no social skills. (YES- there are academic computer scientists who have no social skills!) (I used `he' instead of `he or she' since I have never heard this said about a female established professor.)
5. Is it worth the money the individual spends going to the conference to build the community? Are there other more cost-efficient ways to build community? I do not know; however, I just want to know, for now, is the current system helping to build community albeit inefficiently.
6. Bill Gasarch a long time ago and Daniel Apon recently have had very positive conference experiences in terms of getting into the community (see below). We DO NOT claim these experience are typical. We do not know. But we urge you to share your stories, positive and negative. so that we can get a sense of it. Please be brief, to the point, and not nasty.
   1. Bill Gasarch: I went to a workshop on complexity in 1984 (There was no CCC then) where I met Stuart Kurtz and Ron Book, both of whom were friendly to me. My advisor Harry Lewis introduced me to Alan Selman at STOC (probably 1985). Steve Homer (who I had worked with) introduced me to other people at CCC, including Juris Hartmanis. I met long-time collaborator Richard Beigel at the 1986 CCC. All very positive for getting me into the community.
   2. Daniel Apon: My first conference was STOC 2010, and I bumped into Bill during a coffee break between talks. We had previously been in email contact since he was in charge of handling the travel awards for STOC that year, so it made for an easier ice-breaker. He introduced me to Lance and others. Later, when I went to the Barriers II workshop, I met Aaron Sterling (who is regular participant with myself on the TCS StackExchange site), and we had dinner together one night. I also had the pleasure of meeting a number of other people between the two trips and talking some. Here's a non-exhaustive list (just the first few who come to mind): Eric Allender, Dana Moshkovitz, Scott Aaronson, Andy Drucker, Paul Beame, Anup Rao, and Russell Impagliazzo. My impression of everyone were that they were friendly, open, fun (and smart!) people. It was definitely a positive experience getting the chance to interact with those that I did.

FOCS Part II

I'm heading back to Chicago this morning. Dan Spielman had a special talk in honor of his recent Nevanlinna prize. He gave an amazing talk (as always) about solving Laplacian matrix that comes from graphs, basically putting springs at every edge, nailing down some vertices and seeing where the other vertices end up. Dan's and other talks were filmed, be sure to look for them on the FOCS page in the future.

I spent most of the conference in the hallways talking to people but as someone pointed out to me, I talked almost entirely to people I already knew. I've heard complaints before young people feel they can't talk to senior researchers at STOC/FOCS. We don't do that on purpose, just like to catch up with people we've known for years, but I should try harder to meet the younger crowd.

I had one of those interesting discussions with Ketan Mulmuley on his views on the P versus NP problem (yes we are from the same city but somehow it's easier to talk in these meetings). Ketan talks about his algebraic geometry approach as a very length process towards a solution. Complexity theorists need to give up ownership of the P v NP problem (can anyone "own" a mathematical problem?) and realize that we need the algebraic geometers to help or even lead us in this journey. Ketan also view the journey as more important that the eventual resolution of P and NP. The search for a solution of the Riemann Hypothesis has yet to produce a proof but no one would say that the effort to finding one has been a failure as great math has come from that line of work. The algebraic geometry path to P v NP will yield exciting work as well. 

FOCS Part I

Some thoughts from the FOCS conference in Las Vegas. One result I hadn't seen before I heard people excited by, Determinant Sums for Undirected Hamiltonicity by Andreas Björklund, giving an O(1.657ⁿ) algorithm for testing Hamiltonian Graphs beating the O(2ⁿ) bound of Bellman and Held-Karp from the 60's. 

I spend much more time hanging in the halls than attending talks. And much of the hall discussion focused on the Simons Institute whose letters for intent are due Wednesday. Most major theory groups seem to be putting together a letter, the interest is in what consortiums are forming, i.e., how are the theory groups being partitioned.  Various conjectures about what the Simons Foundation is looking for. For example, will it help or hurt to already have a strong center for theory? What is the right balance of "core theory" and connections to other fields? Should be interesting to see which groups make it to the second round.

Wherever this institute ends up, if run well it will immediately become a major influence in our community. Luca made a good point, that even this process where we all talked to our deans and other administrators about the proposal, helps to sell the importance of theoretical computer science to academic leaders.

I won't give the blow by blow at the business meeting, Suresh already did so on his Twitter. I watched Suresh type furiously into his phone two rows ahead of me and see what he typed immediately on my iPhone. Cool.

This will be the last FOCS with paper proceedings. Luca Trevisan asked some questions about moving to a larger PC or allowing PC members to submit but no one took the bait for a discussion.

The biggest issue came from Dmitry Maslov from the NSF. The Algorithmic Foundations program that funds core theory has one of the highest acceptance rates at the NSF. With the complete turnover of NSF leadership, there is a concern that some might thing theory is over-funded. The CATCS committee is working to educate the new NSF directors that theory funding is going to strong proposals but still it would help to submit more proposals to bring down the rate. Large and small proposals are due soon so submit early and often. If you don't get funding, thanks for taking one for the team. 

New York Area Theory Day- Nov 12, 2010

New York Area Theory Day, Organized by: IBM/NYU/Columbia, External sponsorship by: Google, Friday, November 12, 2010

The Theory Day will be held at Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, Auditorium 109, New York.

For the program see here. For directions, please see here or here (building 46). (ADDED LATER- THE ORGANIZERS SEND ME A NICER PAGE TO POINT TO: here)

My advice: If you CAN GO then GO! If you CAN"T GO then DO NOT GO!

Will there be a 50th CCC? Will you be there?

At the 25th CCC Juris Hartmanis gave a great talk to celebrate having a 25th. Will there be a 50th? I asked people at the conference. What did they say? Watch the video!

So what do you think? Will there be a 50th CCC? Will you be there?

Will there be conferences?

1. Comp Sci may grow up.
2. We may videotape the talks more. Then NSF will stop paying people to go since you can see the talks anyway. So less people will go. This is part of a more general trend where as a society we are sacrificing community for efficiency.

Will there be Complexity theory?

1. The field will still be vibrant, P vs NP will still be unsolved.
2. L=RL may be proven.
3. Some form of the Unique Game Conjecture may be proven or disproven.
4. If GI is in P we may see that proven within 25 years. If GI is not in P then I doubt we'll see that proven within 25 years.
5. If Ketan's Geometric Complexity approach begins to work we may change the name to Conference on Applied Algebraic Geometry and Representation Theory.
6. If we find more and more about what we cannot do and less and less about what we can do, we may change the name to The Barrier's Conference.

A Note from the Trenches (Guest Post from Michael Mitzenmacher)

Former blogger Michael Mitzenmacher talks about being chair and not blogging. In a day for guest posts, over at Geomblog, David Johnson wants to know practical applications of approximation algorithms.

It's been about about seven weeks since I've given up blogging, and I have to say, I do miss it. There's certainly been plenty of things I could have written about, from large-scale CS issues (the Simons foundation call for a new institute for the theory of computing, the NRC rankings and the CRA reaction, new people at the NSF, and the movie the Social Network), more Harvard-centric issues (our intro CS class jumping to over 500 students -- about 200 more than last year, Harvard CS is hiring this year, the Harvard endowment performance (+11%), and the movie the Social Network), to more personal issues (my class for this semester, my take on the CoNEXT PC meeting, my very fun trips to Princeton and UCLA, and why I still haven't seen the movie the Social Network). Each of these could easily have been a post, I'm sure. And I've apparently become terribly accustomed to being able to just announce what I'm thinking (as though everyone should care).

On the other hand, I've been busy. Quite busy. Lots of meetings, lots of answering people's e-mail, lots of solving minor problems, lots of pointing people to the right other people to get problems solved. The start of the academic year is always busy anyway, and my graduate class takes up a fair bit of time even if a good chunk of it is material from previous years, because a good chunk of it is also always new. But the new job as "Area Dean" really sucks up a good bit of time. For the first month, I really don't think I got any research done. This month is better, though much of the research time has been going to revising and finishing off old work rather than new work. Next month I hope it will get better still.

I don't want to say the job sucks. (Well, maybe sometimes it does.) But it does take time, and I'm glad there's a planned exit. As I tell my colleagues, not that I'm unhappy with the job, but only 2.7 more years to go.

On the plus side, there's a lot of positive things going on that I feel like I'm pushing forward. To a large extent, that really seems to be the job: just pushing projects (and the corresponding people) forward, so something gets done. I find things like organizing the class schedule for the next X years and getting a slot to hire don't just happen by themselves, but with the right prodding, they do happen. I'm also blessed with incredibly collegial colleagues, many of whom are going extra miles to make my job easier.

My main management technique is to figure out (or get told) what needs to get done, tell people about it, and then see that it gets done, by me or, hopefully, someone else. I'm getting more used to fixing tasks and delegating them to other people. I also use affirmations constantly. I figure if I tell enough people enough times that something is going to happen, they'll all believe it, and so it will happen. For example, for various reasons for several years we haven't hired new junior faculty. One thing I keep telling people is that after my stint, the question every year at Harvard will not be, "Is CS doing a search this year?", but rather, "What areas is CS focusing its search in this year?" We are doing a search this year; I'm already working to get buy-in on next year's planned search, and it looks very promising; and while it's a bit early to start asking the powers-that-be about year three, I'll start laying the foundation there soon. And see, by telling all of you about it, I'm just in my own positive-thinking (or, alternatively, manipulative) way helping ensure it will happen. Once people accept your basic plan, after that it's just (a lot of) paperwork.

So while I miss blogging, it's been good for me to stop. Besides (desperately) needing the time, it's clear that blogging would give me too much opportunity to say my mind about things brewing before the plans are all fully baked (to mix cooking metaphors). Quietly building consensus doesn't go well with writing a provocative blog. The payoff, I hope, is that you'll be hearing lots of good things about Harvard CS over the next couple of years. After all, we have to get ready for the next round of NRC rankings. I'll try to fire off the occasional update from the trenches, and as for returning to blogging, we'll see how things look in about 2.7 years.

My Trip to Denmark

Last week I had a pleasant short trip to Aarhus, Denmark for the inauguration of the new Center for Research in the Foundations of Electronic Markets. Kevin Leyton-Brown had a more interesting trip to the center.

The Center focuses on real-world pricing mechanisms helped by secure computation building on research of Aarhus cryptographer Ivan Damgård. We heard several talks from government agencies and energy companies, seeing how the electricity network flows through Scandinavia and Northern Europe. Denmark with its many windmills is often an electricity exporter and messy pricing mechanisms come to play.

Dale Mortensen, the Northwestern Economics professor who won the Nobel prize last Monday, spends the falls in Aarhus so the Nobel prize was already big news there. When the local dean officially inaugurated the center, he noted that the center had international partners at Northwestern (Nicole Immorlica and myself) and used that fact to brag about Dale being at Aaarhus not once but twice. He never mentioned the other international partners. Take that Harvard. Dale himself was nowhere to be found.

At the workshop someone ran one of these weird rule auctions that on large scales is essentially a lottery. It costs 5 DKK (about US$1) for each bid. Each bid must be a multiple of 5 DKK. The player with the lowest unique bid pays that bid and gets an iPod Touch. I tried with a random bid. Game theorist Hervé Moulin won the auction. His strategy: Bid on every number from 5 to 75 DKK. A seemingly crazy strategy but with 15 DKK as his winning bid, he got the iPod for all of $18.

Benoît Mandelbrot (1924-2010)

Clouds are not spheres, mountains are not cones, coastlines are not circles, and bark is not smooth, nor does lightning travel in a straight line.—Mandelbrot, in The Fractal Geometry of Nature.

Benoît Mandelbrot, famous for his study of fractals including the one named after him, passed away on Thursday from pancreatic cancer.

I first heard about Mandelbrot as an undergrad in the early 80's as fractals became the mathematical curiosity du jour. One of the popular screen savers on the Sun computers in the late 80's was either zooming in on the Mandelbrot set to reveal the same set inside. One could spend hours watching--this and Tetris wasted many grad student hours in those years before Facebook and Twitter.

I saw Mandelbrot speak just once in 1996 at a 50th Anniversary of CWI celebration, also the only time I've seen Knuth give a talk. All I remember from the talk were pretty pictures of imaginary fractal mountains on other planets generated by Mandelbrot for some movie--shades of Avatar.

I always thought of fractals as mostly descriptive--yes, fractals appear almost everywhere, but so what? Nevertheless here's to a very uncommon mathematician who literally showed us the beauty of mathematics.

How hard is this problem?- I ask this non-rhetorically

I recently saw the following puzzle:

Which two numbers come at the end of this sequence? (That is, what are x and y?)

2,4,6,30,32,34,36,40,42,44,46,50,52,54,56,60,62,64,x,y

(NOTE ADDED LATER- I had a typo in this post, the worst kind of typo one could have- I had a 5 instead of a 6. I looked up the original source and they had the same typo. SORRY!)

I could not figure it out. I went to the sequence-website which gave me the answer. Before the web I would not have been able to do this and I may have had to wait until there was a web to look it up on in order to solve it. Or maybe I could have solved it, though seeing the solution I doubt that.

How hard is this problem? How to tell how hard it is? How well known is this puzzle? YOU can help me!

1. Try to solve it without using any other resources.
2. Leave a comment either saying either I solved it without any help OR I was unable to solve it OR I knew how to solve it since I already saw it.
3. Please do not include the solution. I will not post a solution--- if you are curious just type it into the sequence website.
4. Please do not lie. I want to use this to judge how hard this problem is.

Two Candidates for an Ig Noble in Mathematics

(This is a sequel to my post on the Ig Nobel Prize.)

Two candidates for an Ig Nobel prizes in Mathematics. They deserve it for opposite reasons. (They are old results and hence, I assume, do not qualify.) (ADDED LATER- I checked with the Ig Nobel Committee- they DO allow old results to be submitted and have even given the prize out to people who are dead.)

1. The Banach Tarski paradox deserves an Ig Nobel since it is obviously false.
2. The Jordan Curve Theorem deserves and Ig Nobel since it is obviously true.

The NSF Takes Shape

As I've mentioned before, the NSF is turning over top to bottom especially in computer science. Most of the pieces are now in place so let's check out the new personnel at the NSF that affect theoretical computer science.

The Senate has now confirmed MIT Dean Subra Suresh as the new NSF Director. Suresh replaces Arden L. Bement, Jr.

Michigan CSE Chair Farnam Jahanian takes over as Assistant Director of CISE (as in assistant to Director Suresh) starting in February. Jeannette Wing went back to Carnegie-Mellon last summer. CISE covers computer science funding at the NSF.

Purdue professor Susanne Hambrusch heads the Division of Computing and Communication Foundations (CCF) which includes theoretical computer science. Sampath Kannan returned to Penn.

The other divisions at CISE have new leadership as well. UCSD Chair Keith Marzullo heads Computer and Network Systems (CNS) and CMU Vice Provost for Research Computing Howard Wactlar heads Information and Intelligent Systems (IIS).

The CCF program directors handling the Algorithmic Foundations proposals from last month are Mitra Basu, Tracy Kimbrel and Dmitry Maslov. The NSF is still working to replace Richard Beigel who specialized in computational complexity and has recently returned to Temple.

What do all these changes mean for US funding for computer science and theory in particular? We'll just have to wait and see.

Noble and Ig Noble Prizes

What is the Ig Nobel prize? To quote the website:

The Ig Nobel Prizes honor achievements that first make people laugh, and then make them think. The prizes are intended to celebrate the unusual, honor the imaginative --- and spur people's interest in science, medicine, and technology.

Some science seems real, though odd: In 2006 the Ig Nobel in Mathematics went to (quoting the website)

Nic Svenson and Piers Barnes of the Australian Commonwealth Scientific and Research Organization, for calculating the number of photographs you must take to (almost) ensure that nobody in a group photo will have their eyes closed.

Some science does not seem real: In 1993 the Ig Nobel in Mathematics went to (quoting the website)

Robert Faid of Greenville, South Carolina, farsighted and faithful seer of statistics, for calculating the exact odds (710,609,175,188,282,000 to 1) that Mikhail Gorbachev is the Antichrist.

There is no specific Ig Nobel prize in computer science. What computer science work deserves an Ig Nobel? What complexity work deserves an Ig Nobel?

Has anyone every won BOTH an IG NOBEL PRIZE and a NOBEL PRIZE? YES! It just happened! Andre Geim won the 2010 Nobel Prize for Physics and had previously won 2000 Ig Nobel Prize for Physics. I describe the equipment used in both, but I will not say which one won the Nobel prize and which one won the Ig Nobel prize.

1. One used Magnets and Frogs.
2. One used Scotch Tape and Pencils.

Partha Niyogi (1967-2010)

University of Chicago Computer Science and Statistics Professor Partha Niyogi passed away on Friday after a battle with brain cancer. Partha worked in machine learning in a number of theoretical and applied areas, particularly memorable for his use of manifold theory in semi-supervised learning.

I knew Partha well from my years at Chicago. It's hard to lose someone who was a close colleague and friend, especially when they die so young. A great loss.

The Annual Fall Jobs Post

The CRA is working on setting guidelines for job deadlines to help out with some of the gridlock in the job market. Many of the top departments have already moved their deadlines for full consideration to early December or November. Keep an eye out and remember to apply early this year.

Possible theory tenure-track faculty jobs at Harvard, Rutgers, TTI-C and Federal University of Rio Grande do Sul (Brazil). For more faculty and postdoc listings: CRA, ACM, Theory Announcements and CCI. Also check out web pages of departments that interest you.

A little early to tell but this year will likely be similar to last year: a small number of tenure-track positions in TCS and a large number of postdoc positions. Out of necessity almost everyone does a postdoc now and many people doing a second or third as well.

Have the theoretical computer science community actually moved to postdoc culture, where people are now expected to do a postdoc (or multiple postdocs) before taking a tenure-track position like physics, chemistry and biology? When did the field make that jump?

NRC Rankings

The NRC "rankings" of Graduate programs was released yesterday. I put up a Google spreadsheet of the CS rankings. Phds.org will also generate rankings using various criteria.

You are not getting actual ranking from the NRC rather two ranking ranges: Statistical-based (R-ranking for "Regression") and Reputation-based (S-ranking for "Survey"). For example, Northwestern CS has a 90% chance of being ranked between 42nd and 73rd (R-ranking) and between 26th and 69th (S-ranking).

Even with these wide ranges there are a number of problems in CS rankings: no citation information is being used, the data is five years old and much of the information is inaccurate (as the Pontiff complains). A simple sanity check on any ranking of CS departments would list the top four as some permutation of MIT, Berkeley, Stanford and Carnegie-Mellon. Congrats to Princeton for breaking this check.

Why no citation information? The NRC originally used the ISI data which didn't cover most conference proceedings that computer scientists consider their main venues of publication. After some discussions with the CRA, the NRC admitted this as a problem and decided to ignore CS publication data citing lack of time to find a different approach.

Yesterday the CRA released a statement on the reliability of the CS rankings.

CRA is pleased that the NRC acknowledges there are errors in the data used to evaluate computer science departments and that, in the words of NRC Study Director Charlotte Kuh, “There’s lots more we need to look at for computer science before we really get it right.”

Schools are taking the opportunity to promote their rankings. Northwestern Engineering boasts how well they did with some nice charts. We're certainly not the only ones.

Did the NRC fulfill their main mission of giving a valuable alternative to the US News rankings? US News uses a "wisdom of crowds" approach by just surveying department and graduate program chairs. The NRC tried a scientific approach which led to years of delays, many complaints about methodologies and accuracy, and a lack of a true ranking. After all the measures we can feed into a formula, the one thing that draws students and faculty to a department is its reputation. Complain as you will about US News, they do try to capture that one statistic.

Meanwhile what do I say to prospective graduate students who cite the low Northwestern CS numbers? I could mention the problems in the methodology, point to the CRA statement, say the numbers are based on data that predates most of the theory group. More likely I will fall back to that trite but true statement: You shouldn't choose a graduate program for their numbers, but for their people.

Review of Lipton's Book-Blog/Review of Goldreich and Arora-Barak/New Book Review Column/Do you want to review?

1. My review of Lipton's new blog-book is here. It will appear in my SIGACT NEWS at some later time.
2. Daniel Apon's joint review of Computational Complexity: A Conceptual Perspective by Oded Goldreich and Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak is here. It will appear in my SIGACT NEWS at some later time.
3. My latest SIGACT NEWS book review column (along with all of my other SIGACT NEWS book review columns) can be obtained from here (Ignore the list of books I want reviewed. See next item.)
4. HERE. is a link to the list of books I want reviewed If you see a book you want then email me at gasarch@cs.umd.edu the name of the book and your postal address. We will then work out details over email- when the review is due, and whether me or the publisher sends it to you. Before volunteering you should read my advice for reviewers. Here is the LaTeX Template.

The Theory Social Network

Derrick Stolee tweeted that the videos from the 2010 Complexity Conference are now on-line. If you want to attend a conference live, don't forget early hotel and conference registration for FOCS ends Thursday. Hope to see you there.

On a related topic, I once wondered if we could have a "virtual complexity coffeehouse" where researchers could electronically drop in, talk research and other stuff. I even once played with Second Life on the hope that one could create the coffeehouse there, but found that environment wanting.

The new Q&A site (http://cstheory.stackexchange.com) comes reasonably close, the format of the communication seems to generate real discussion about various problems and interest among the community. I know it's working because I've already had to tell one of my students that he spends too much time there. Now, if they also had some discussions on controversial issues, advice on living the theory life, and dispensed a good latte we'd be all set.

Theorems that are less interesting because they are more interesting

(This post was inspired by Joe Kruskal's passing. Kruskal's tree theorem, trees under minor are a well quasi order, relates to example 2 below.)

There are some theorems that seem less interesting once you generalize them. I am not sure they are less interesting, but they seem that way. Here are some.

1. In 1978 I told my number theory professor that there is a polynomial in many variables with integer coefficients such that the positive numbers in the image are exactly the primes. He thought that was interesting! Maybe it uses algebraic number theory! or cyclotomic fields! or some deep number theory! I then told him that for any r.e. set A there is a polynomial in many variables with integer coefficients such that the positive numbers in that set is exactly A. You prove this by coding Turing Machines into polynomials. No hard number theory needed. It uses some easy number theory and many tricks. He was much less interested. (The result comes from the machinery used to prove Hilbert's Tenth Problem.) Jones came up with the actual polynomial. See here.)
2. It easy to show that if L is regular (CFL, c.e.) then SUBSEQ(L) is regular (CFL, c.e.). What about if L is decidable? The good news: if L is decidable then SUBSEQ(L) is decidable. That sounds surprising and interesting. It is not. Actually if L is any language whatsoever then SUBSEQ(L) is regular. (High Level Proof: subsequence is a well quasi ordering, hence any downwardly closed subset of Σ^*, such as SUBSEQ(L), has a finite obstruction set. This finite obstruction set can be used to give a DFA for SUBSEQ(L).) What I really want to see is a proof of L decidable implies SUBSEQ(L) is decidable that comes from recursion theory. I don't have one. I'm not even sure what that would mean. Show that SUBSEQ(L) is both c.e. and co-c.e.? (For more information see this post of mine.)

If you know theorems that are less interesting because they are more interesting, then please comment.

The World in Its Own Terms

The New York Times Magazine last Sunday focused on technology on education. Lots of good reads but what caught my eye was an article by Microsoft Research's Jaron Lanier, basically arguing that computational thinking ruins your enjoyment of life.

A career in computer science makes you see the world in its terms. You start to see money as a form of information display instead of as a store of value. Money flows are the computational output of a lot of people planning, promising, evaluating, hedging and scheming, and those behaviors start to look like a set of algorithms. You start to see the weather as a computer processing bits tweaked by the sun, and gravity as a cosmic calculation that keeps events in time and space consistent.

This way of seeing is becoming ever more common as people have experiences with computers. While it has its glorious moments, the computational perspective can at times be uniquely unromantic.

Nothing kills music for me as much as having some algorithm calculate what music I will want to hear. That seems to miss the whole point. Inventing your musical taste is the point, isn’t it? Bringing computers into the middle of that is like paying someone to program a robot to have sex on your behalf so you don’t have to.

And yet it seems we benefit from shining an objectifying digital light to disinfect our funky, lying selves once in a while. It’s heartless to have music chosen by digital algorithms. But at least there are fewer people held hostage to the tastes of bad radio D.J.’s than there once were. The trick is being ambidextrous, holding one hand to the heart while counting on the digits of the other.

Lanier is mostly upset that a computer can predict his likes and dislikes so easily. Sorry Jaron, you are just not as complex as you thought you were.

Joseph B Kruskal passed away (Guest post by Clyde P Kruskal)

(Guest post from Clyde P Kruskal.)

Yesterday (September 19, 2010) my uncle, Joseph B. Kruskal passed away. I just wanted to say a few personal words. Maybe, later, someone will discuss his work. Although he is famous in computer science for Kruskal's Algorithm and Kruskal's Tree Theorem he was not primarily a computer scientist. He was also a statistician and psychometrician.

I recall as a child how happy I was when he came to visit, usually after giving a talk somewhere. I also remember that once, when our extended family had a get together on the Long Island Sound, he spent all day taking the children one-by-one out sailing.

I always knew the three Kruskal brothers were well-known mathematicians. But it still surprised me the first time I actually saw my uncle's work referenced in a book. I was in college working at a summer job, learning some graph theory, which at the time I knew nothing about. As I turned the page of the book, there was Kruskal's algorithm! I had never heard of it until then.

Now I have the pleasure of teaching the algorithm in my classes. I used to think that when I got old enough I would be able to fool students into thinking that it was actually my own, but it never quite worked out that way.

I did use his theorem on Totally Unimodular Matrices that he co-authored with Alan Hoffman, in a paper I wrote with Marc Snir. When I told Joe we were referencing the theorem, he told me that he rarely collaborated on research, but this was an exception, which he very much enjoyed. When looking up the reference just now, I found an interesting description of their collaboration, which confirmed how I recalled it.

There was a period of time when I used to visit Bell Labs, where Joe worked. I would stay with him and my Aunt Rachel, who were wonderful hosts. I used to enjoy our wide ranging dinner conversations, and I learned so much about words, politics, statistics, my family, etc.

I apologize if this is a bit disjointed. It makes me feel better having written it on this very sad day.

Should You Mentor High School Students?

I have mentored many high school students on projects (21 in the past, 6 right now). Is this a good use of ones time? I note my experiences and advice- if you have different experiences and advice, feel free to share.

1. Unlike PhD students you don't have to worry about the job market, support money, or if they prove something original.
2. I have not gotten papers out of it. Even very good students lack a certain maturity for paper writing. (There have been exceptions.)
3. It is good of society. (The most important problem facing society today, that I can do something about, is that not enough high school students know Ramsey Theory.)
4. By explaining material to them it has helped me sharpen my own understanding.
5. Most of the students I have advised have been pretty good mathematically (they already know discrete math and induction and how to prove things). Some have been good at coding which also comes in handy. Most have come from Blair High School's Magnet Program. (They have a very strong physics department which specializes in Magnetism.)
6. Having students do a project where they can code some stuff is good in that SOMETHING will come of it. Also, this may be something you wouldn't normally do so it may help you.
7. The standards of what is original are different on this level. The project does not have to really be original in the sense we would mean it. If they work out something that you already know the answer to and write it up that's fine. It may be more accurate to call it a research experience.
8. The mostly did projects that DID NOT require a lot of background. Even if they are very good, they are unlikely to have a lot of background. This is why many of them have worked in Ramsey Theory. You may be saying but bill, you like Ramsey Theory anyway. True- but one of the reasons I got interested in it was to help mentor high school students. Its a chicken-and-egg thing. (This metaphor may die soon as scientists now think the chicken came first.)
9. The student of mine who has gone the furthest in Math is Jacob Lurie. who is now a full professor at Harvard (in Math). He didn't need much help; however, I did help him learn some recursion theory (we went through all of Soare's book) His project was on Recursive Surreal Numbers.
10. Many of my students enter various contests. For every thousand dollars they win, I get a free lunch. (If Jacob wins the Fields Medal I'll get 15 free lunches!)
11. Recruitment. Some of my mentorees have come to UMCP, though that is not really on my mind when I agree to be a mentor.
12. Why have I mentored so many? I have never sought them out--- they find me since I have mentored people in the past. Also, if a HS student comes around and wants a mentor they are often pointed to me.
13. Should you mentor high school students? It is unlikely to help you with your research program (there are exceptions). But if you do mentor high school student then (1) make sure its not a big time sink, and (2) use it to learn or relearn results you've forgotten (Recently I was forced to relearn the Erdos-Szekeres Theorem).
14. So, what have they worked on. Including this years gang and their tentative projects here is the breakdown:
    1. 11 worked on Ramsey Theory (3 of these worked together).
    2. 3 worked on Duplicator-Spoiler Games (together).
    3. 3 worked on Empirical Algorithms (2 of these worked together).
    4. 3 worked on Crypto.
    5. 2 analyzed some Simple Games.
    6. 1 worked on Recursive Surreal Numbers.
    7. 1 worked on Graph Isomorphism.
    8. 1 worked on Monotone Circuits.
    9. 1 worked on the Prob Method.

How Can You Spend $150 Million?

Suppose you happen to have $150 million burning in your pocket that you want to use to help the theoretical computer science community ($150 million endowed will bring in about $6 million/year) How would you use it?

• Create an Institute for Theory of Computing?
• Endow a few theory conferences?
• Create a 150 millennium prizes?
• Build a fancy new CS building?
• Endow 25-30 professorships or a 75-100 postdocs?
• Hire lots of Fields medalists at ridiculous salaries only if they spend all their time working on the P v NP question?
• Something else?

This is all hypothetical, I don't known anyone, outside of the Simons Foundation, who has $150 million ready to spend.

$150 million doesn't go as far as it used to. In 1992, Henry Rowan gave $100 million to Glassboro State College in New Jersey, now called Rowan University. How much would it cost to get your name on a university today (say at a large private Midwestern university with a geographically confusing name)?

FOCS Travel Support (Guest Post by Paul Beame)

The program for the FOCS 2010 has an excellent set of selected papers and in addition has tutorials on Saturday by Ketan Mulmuley, Mihai Patrascu, and Tim Roughgarden, a memorial for Avner Magen, and an invited talk by recently announced Nevanlinna Prize winner Dan Spielman.


Through two different sources, NSF and IEEE TCMF, there is substantial support for student and postdoc travel and registration for FOCS 2010.  

Travel awards ($15K from NSF)   Students and some postdocs at US institutions.

• One travel award per institution
• Up to $750 per attendee

Student registration awards (>= $3K from IEEE TCMF)

• Apply by September 23
• Notification by September 28
• No requirement for US institution or limit per institution

See the Travel-Support page for how to apply.   

The hotel reservation deadline and the early registration deadline for FOCS 2010 are both September 30.

A Mathematical Urban Legend

I have heard the following story many times in many versions:

A PhD student in Math at PRESTIGIOUS SCHOOL was defending his thesis which was in REALLY ABSTRACT AREA and BIG SHOT IN THAT AREA was in town and decided to go to the defense. At the end of the defense BIGSHOT said The object you are studying is NOTION OF TRIVIAL FOR THAT OBJECT.

I've heard this with PRESTIGIOUS SCHOOL being Harvard, MIT, or Princeton. I've heard it with REALLY ABSTRACT AREA being Category theory, Algebraic Geometry, Topology, or Logic. I've heard it with NOTION OF TRIVIAL being the empty set, any finite set, a 1-point space, or an inconsistent system of axioms. I have not heard all possible combinations. For example, if the area was algebraic geometry, it is unlikely that the notion of triviality be an inconsistent system of axioms, unless the teller got his legends wrong.

Is this a pure math pure urban legend or was there ever a case like this? I suspect that it is pure fiction. You may be thinking: Math is so abstract that it could have happened. True enough, but do not confuse what could have happened with what did happen.

Like most urban legends the story persists because, while it may be false, the point it is making--- math is so abstract it is possible to lose track of what you are talking about--- has some truth to it.

If this story is true or even mostly and you KNOW this then please leave a comment to that affect.

The Rubik's Cube Conjecture PROVEN! (Do we care?)

In 1994 Fermat's last theorem was proven! In 2003 Poincare's conjecture was proven! In 2010 the Rubik Cube Conjecture was proven! That is, it was shown that the minimum number of moves needed to solve Rubik's Cube is 20 (it was known that there are starting configurations that require 20). Here is the pointer: Rubiks Cube has been solved. (Jeff Erickson also had a blog entry on Rubik's cube lately: here.)

(ADDED LATER. Clarification: From any starting position one can get to the solution in \le 20 moves. There exists a starting position where every solution takes \ge 20 moves. )

We all have a sense that the Rubik Cube result is not as important as the other two. What makes a math problem important?

1. Would Martians work on it? I suspect Martians would work on FLT and Poincare but not Rubik's cube. One of the first things I would ask Space Aliens is what Math they have done.
2. Does it connect to other parts of mathematics? This leads to a seemingly circular definition of importance: A topic in math is important if it connects to other topics that are interesting. FLT and Poincare's conjecture are connected to other parts of mathematics. One way to understand Rubik's cube is through group theory; however, this is not so much a connection as an application. Rubik's cube studies have not lead to advances in group theory.
3. Does the problem have its origins in some real world phenomena? (This is not necessary but helps.)
4. The problem should be hard but not so hard that you cannot make any progress on it.
5. The proof must be interesting (hmmm- then we need to define interesting).

These criteria may be too strict. It would be interesting to discuss other branches of math that are considered important that do not quite fit these criteria and see what else makes them important. Or branches that do fit these criteria but are not considered important.

How to Write Up Major Results

First some conference news: FOCS conference and hotel registration available on line, early deadline is September 30. STOC 2011 website is up with the CFP, deadline November 4. For more news follow the SIGACT Twitter or Facebook.

Deolalikar's paper caused a stir in the community partly because it was written better than the usual P versus NP proofs we see. But the right comparison is to papers that have settled major questions, such as Agrawal, Kayal and Saxena's Primes in P and Omer Reingold's Undirected s-t Connectivity in Log Space.

Both those papers needed to be convincing right off the bat and they both were. First notice the algorithms (page 3 in AKS and pages 9-12 in Reingold). No vague outline, no "should be able to", just very specific algorithms that one can analyze. Reingold only uses one "clearly" for the simple initial transformation from an adjacency matrix to  a rotation map.

Both papers have to make two arguments, that the algorithms work in the claimed time/space and that they work correctly. In AKS, Section 4 shows the algorithm works correctly and Section 5 (using Lemma 4.3) show the algorithm runs in polynomial time. Section 4 is broken into a series of lemmas, each easily checkable with a limited knowledge of algebra. In Reingold the tricky part is getting the algorithm exactly right so that is uses logarithmic space which is carefully analyzed in his Sections 3 and 4. The correctness proof (based on earlier work) is a rather short Lemma 3.2 but Reingold does go over much of that background in Section 2.

In both these results it took an amazing ingenuity to discover these algorithms, but it wouldn't take more than an undergraduate math major to check the proofs.

Showing that P ≠ NP will be a much more difficult task, instead of coming up with a single algorithm, one has to show that no possible algorithm can solve some specific problem in NP. But even though the proof will be harder, the write-up needs to be just as understandable and easy to follow as AKS and Reingold. The community needs a proof we can verify step by step so that we can either be convinced of the proof or find the problem in the proof. If there is a jump in logic that one cannot verify the author has failed in his or her write-up.

Proving P  ≠ NP will require pure genius but you shouldn't need a Fields medalist to verify the proof.

CS Happenings

Yesterday I was at a meeting of the CCC Council, add in a couple of emails and I have lots of short notes on CS stuff.

In these meetings I get to hear about CS research beyond theory: High-performance (i.e. very fast) computers, computing at the margins (guess what it is before you click), CS roles in energy and health and the debate on the Venn diagram of robotics and cyber-enabled physical systems. Question of the day: If you walk in a room and a sensor turns on a light, does that count as a robot?

Did you know that you can plug devices into a single spigot and electrical outlet and via machine learning techniques determine water and electrical activity in your home. Sure there are real applications for energy conservation but how about the automated Facebook posts.

Lance has just flushed the toilet but failed to turn off the bathroom lights.

Ed Lazowska send around a 1998 piece by Bob Lucky on electrical engineers with the worry that CS might not be far behind.

Projecting the current trends, future computers will consist of a single chip.  No one will have the foggiest idea what is on that chip.  Somewhere in the basement of Intel or its successor will be a huge computer file with the listing of that chip.  The last electrical engineer will sit beside the file, handcuffed to the disk drive like a scene out of "Ben Hur."  That engineer will be extremely well paid, and his or her every demand will be immediately satisfied.  That engineer will be the last keeper of the secret of the universe: E = IR.

The NRC Graduate Assessment Report will be released on September 28. What will be the top ten CS departments? The report won't tell you, rather giving multiple ranking ranges based on five-year old data. Prepare to be disappointed.

Slides from the Snowbird meeting I posted about in July are now available including a vidcast of Sally Fincher's wonderful talk on CS education. On the topics of talks, you can now watch the video of the STOC tutorial talks and ICM Talks (see also Gowers).

Richard Beigel asked me to pass the following note:

PIs who receive awards or funding increments after January 3, 2010 will be required to upload a Project Outcomes Report within 90 days after their award expires.  These reports are for the general public and will not be edited by NSF.  PIs will be able to follow a link from fastlane in order to upload their reports.  Because public support for science is very important, I would ask PIs to polish these reports and include images (with permission from the owner). To the best of my understanding, NSF PIs can continue to upload all required reports via fastlane and can ignore the login instructions in the link for grants.gov. 

Intelligent questions about the alleged P NE NP proof

People have asked me how much the alleged proof of P NE NP was discussed at Barriers II. Actually, nobody discussed the proof; however, we did discuss the aftermath. Most of the discussion was about the same questions I had posted a few days ago. In fact, here is a direct quote: Your post mixed interesting questions, which were ignored, and stupid thoughts, which is all anyone commented on. Why don't you repost just the interesting questions?

SO, here is that posts questions, minus the stupid things I said, plus things I heard at the conference.

1. Why did this proof get so much attention before it was verified? Because Lipton and Cook took it seriously.
2. Was this all good for the community? YES- more people know what P vs NP is. YES- if Gowers and Tao now begin working on it more. YES- stone soup.
3. Do mathematicians care about complexity theory? The answer is surely yes, but how strongly? Is the answer yes or Yes or YES or HELL YES! ? If you count number-of-mathematicians then its hard to say. If you take a weighted sum based on quality of mathematicians then Gowers and Tao alone make the weighted sum enormous. In any case, when did the change happen? Was it drastic or slow?
4. If someone claims to prove a big result and its public and problems are found with the proof, should they retract? If so then by when? One thing problematic with the question is the word should. Should for the good of the field? Should for the good of ones own career? Should if you want to be taken seriously? If someone has minor mistakes and just needs a little more time to fix them then a retraction is not needed. But the terms minor mistakes and a little more time are not well defined.
5. How much progress has been made on P vs NP? Scott thinks so. (See the talk Has there been progress P vs NP which is on his homepage.)
6. Have there been hard math problems that were solved all-of-a-sudden without any real prior results or plan? Finding and intermediary c.e. degree was such a problem, but it wasn't anywhere near as hard or as important as P vs NP.
7. What criteria SHOULD we use to determine if a proof of a major result is worth looking at?
8. What criteria DO we use to determine if a proof of a major result is worth looking at?
9. Has Descriptive Complexity Theory been ruled out as a way to solve P vs NP (something like oracles or natural proofs)?
10. The story about the story has reached the New York Times: here

Report from Barriers II Part 1

On Thursday Aug 26 Lance stated Bill is at Barriers II in Princeton and promises a full report upon his return. Not quite sure I promised that, or what a full report would entail, but here goes.

1. When I first heard there would be a BARRIERS II workshop I assumed it would be full of Oracle results, Natural Proofs, Algebrazation, maybe some speculation on independence results (I do not think we have any right now). And indeed, this was at least part of the agenda for Barriers I. (See here for a blog about Barriers I.) Barriers II was (1) Approx algorithms and lower bounds, (2) Crypto, (3) Quantum Computing, (4) Communication Complexity, (5) Geometric Algorithms (NOTE- NOT Ketan's Geometric Complexity Theory program). However I can't say it was false advertising since the program was on the web early enough that one could see what one was getting into. It was misnamed.
2. The organizers told me that it was called Barriers because the speakers were urged to talk about where the field is and where it is stuck. I think talks like that have a name already: Open Problems, or Directions or whatnot.
3. All of that aside, how was it? It was WONDERFUL!. The talks were uniformly good. They were mostly survey-talks so one outside the field could follow them (that was the intent). This also lead to the following oddity: the day on (say) Quantum had very few quantum people at it (except the speakers) since your standard quantum person has probably heard the talks before or at least knows the material.
4. Approx Alg and lower bounds: I was inspired to actually learn what Semi Definite Programming and Iterative Methods are. I finally understand the UGC and its different formulations. Dana Moshkovitz gave a nice rump session about a promising route to PROVE UGC. This was not one of those we doubt it will work but the approach is still interesting talks (this could be a rallying cry for our field) but seemed like a real plan.
5. Crypto: Lattice stuff and also stuff about: If your key leaks slowly can you still do crypto? (yes).
6. Quantum: Scott introduced the speakers and was the first one. He had a slide warning us to NOT PANIC at the mention of Quantum. All of the talks were outreach--- why complexity theorists should learn quantum methods. I blogged about this non-technically here. One key point I will re-iterate: Even if you don't work in quantum computing you will need to learn their methods. (Analog: even if you don't work in prob you need to know the prob method.) Over dinner we noted the following: there are many quantum books for the layperson but there are few (none?) complexity books for the layperson (hurry up Lance!). Why is this? Quantum seems less abstract then Complexity and some laypeople may thinks they have a notion of it. They may be wrong.
7. Communication Complexity: Paul Beame gave an hour long talk where he went over the entire Kushilevitz-Nisan book. (NOTE: This book is on Lance's list of favorite computational complexity books.) How did he do it? He skipped some stuff. (I recommended talking fast. Fortunately he didn't take my advice.) The other talks were applications of Communication Complexity to lower bounds on data structures (not quite- some of the lower bounds didn't use Comm. Comp.), data streams, direct sum problems, and a talk on quantum comm. comp. This raises the question: Is Communication Complexity only interesting when it applies to something else, or it is interesting for its own sake? I proposed the following open problem in a rump session, though it seems like its already out there (that is, its not really MY open problem).
   

   Alice has x, Bob has y, both are n-bits long. We are promised that PARITY(x)=0 and PARITY(y)=1. Alice and Bob want to find i such that x_i ≠ y_i with d rounds (d a constant) and O(log n) bits-per-round. Show they cannot do this. ANSWER: We already know this statement is true since it is equivalent to PARITY ∉ AC₀. (Using Karchmer-Wigderson games, another game that is not much fun.) However, I would like a communication complexity proof of this which would give an alternative proof of PARITY ∉ AC₀. In particular it would give a top-down proof instead of a bottom-up proof.

8. Geometric Algorithms. Paul Beame said that this session would be a nice counterpoint to the communication complexity talks since the Geometric Algorithms session would prove some upper bounds on problems that the Comm. Comp. Session proved lower bounds on. (Mike Sipser once told me It is good to do an algorithm as a sanity check on your lower bounds.). Alas I had to take off that morning so I don't know if this really happened; however, I assume that it did.
9. Not much talk about the alleged P NE NP proof; however, I will discuss what was discussed in my next blog.

New Institute for Theory of Computing

The Simons Foundation has announced a competition to establish a new Institute for the Theory of Computing in the United States.

Computation (and its abstract form, the algorithm) has not only revolutionized science, technology, and society, but also is among the most important scientific concepts discovered and developed in the 20th century. This scientific discipline has enabled numerous technological advances and has forged many connections to mathematics and other sciences, providing fruitful insights and new problems. It has impacted not only computer science and technology, but also parts of mathematics, physics, biology, economics and sociology. Meanwhile, its core scientific agenda is extremely ambitious and challenging. In short, this theoretical field is one of the most exciting and important today, attracting excellent young talent to its ranks at a growing rate. Young people with education and training in this field are well positioned to make central contributions to computer science and science in general.

An institute focused on the theory of computation could bring together a critical mass of researchers from around the world to accelerate fundamental research on computation and to further develop its interactions with other areas of science ranging from mathematics and statistics to biology, physics and engineering. The Simons Foundation invites applications for grants to establish such an Institute.

Letter of intent due by October 27 and full proposals by next June.

It's the funding that catches the eye, $6 million/year for 10 years with possible renewed funding or endowment after that. To understand the scale, that's roughly the budget of TTI-Chicago. This new institute will play a major role in our field.

The institute will be modeled on the Kavli Institute for Theoretical Physics, MSRI and the IMA (also similar to DIMACS) which are located at or near major university campuses and host programs on a given topic for several months to a year with long-term visitors and have several workshops related to those program topics.

This is opposed to the Oberwolfach/Dagstuhl/BIRS model of an isolated location with on-site room and board, weekly workshops but little to no long term programs or visitors. I'm glad the Simons Foundation is going with the former model. While I've enjoyed the many Dagstuhl workshops I've attended, centers like DIMACS tend have a greater long term impact on the field.

Where will this institute be located? We'll find out next fall. Should be exciting.

Theory Journals

I got the following request from a reader.

I have a question about TCS journals. As I am trying to follow your advice on being more diligent about journalizing my papers, I realized that I am surprisingly ignorant about where to send them. A couple of more senior colleagues I asked didn't really have the answers.

What are the journals that accept theory papers? What's their specialization (if any)? What's their relative quality/reputation? What's the expected turn around time for each of them? Anything else I should be asking?

Sounds like a list that should be on a site we can edit in the future like Wikipedia and in fact they have such a list. It can use some additions, links, publishers and specializations if anyone is so inclined to help update it. Most of these journals cover general theory unless their title indicates otherwise.

For reputation I put JACM first, followed by SICOMP, followed by a rough equivalence class of the most of the others. Information Processing Letters has only short papers, good for a result that has a simple proof but still worth writing up.

Turn around time depends more on the editors and the referees than the particular journal. The average time from submission to publication (assuming no major issues found in the referee process) is a bit over a year with a very large variance. Feel free to ask/bug the editor if you need faster publication. 

Another big issue to consider is which publisher to choose. It can affect who can access your paper, where it will be indexed and archived and how and whether the paper will appear in print and/or on the web. I'm a (biased) fan of the ACM with its well-organized low-cost digital library but there is something to be said for open-access journals.

Cryptography if P = NP

Bill is at Barriers II in Princeton and promises a full report upon his return.

Ask many computer scientists what happens if P = NP and you'll get the response that it will kill cryptography. Let's ignore solving all optimization problems, solving AI and learning everything, likely cures to many diseases and many more amazing advances in society, what a disaster it will be that we can't send secret messages to each other.

I don't at all believe P = NP but let's have this hypothetical discussion of what happens to cryptography in that world. We do lose public-key cryptography, the ability for two people who have never met to electronically still send encrypted messages to each other. How will I send my credit card info to Amazon if P = NP?

Amazon will send me a USB key containing a gigabyte worth of a one-time pad, enough to encrypt all my transactions for my entire life (even though I will live much much longer thanks to P=NP). This might work for Amazon but what about tiny mom and pop web stores? We just need a trusted site for a one-time pad registry so my USB key will work for any Internet transaction. Even for public-key cryptography today we need trusted parties to verify sites so we haven't lost much here.

For large financial institutions they can ship huge amounts of one-time pad data through secure couriers (or just ship data this way). Large amounts of compressed data can have a very small footprint these days.

What about cryptographic protocols? Zero-knowledge is uninteresting if P = NP. Many secure multi-party computations can be done with private channels which just need private keys. There are many others, electronic money, secure voting and digital signatures come to mind, that seem difficult to do if P = NP. On the other hand they are also hard to do in practice today even under the usual assumptions.

Certainly P=NP will make cryptography considerably more painful that it is now and many things we thought previously encrypted won't be anymore. But we'll figure out how to meet our crypto needs in any environment. The loss of public-key cryptography shouldn't be our first gut reaction to what happens if P = NP.

***SORELLE*** PHD!!/Workshop on Boolean Threshold Functions/NSF program

Three annoucements (the last two I was asked to post)

ANNOUCEMENT 1: Congrads to fellow blogger ***SORELLE*** who got her PhD recently. I was on her committee. She did a masterful job of presenting it. It looked like theory that can be applied to stuff. At least Google, who hired her, might think so. Or they might think (correctly) that she is smart and knows things so she can help them. See her post about her PhD for more information and a pointer to her actual thesis.

ANNOUCEMENT 2: Rocco Servedio and Ryan O'Donell have requested that I post about upcoming workshop at the Center for Computational Intractability in Princeton.

The topic is Analysis and Geometry of Boolean Threshold Functions. It will take place the Thursday and Friday morning before FOCS, Oct. 21--22. For detailed information, please see: here There is also a poster here.

COMMENT FROM GASARCH: Its right before FOCS but its NOT close to FOCS. It is in Princeton NJ. FOCS is in Las Vegas. Not sure this makes sense but I suppose they will find out.

ANNOUCEMENT 3: Tracy Kimball at NSF has requested this annoucement be posted.

CISE has announced a new funding opportunity administered jointly with the Directorate for Social, Behavioral and Economic Sciences (SBE). The new program is called ICES (Interface between Computer Science and Economics and Social Sciences). You'll find the all the details about ICES here. Be sure to read the whole solicitation and click through to the non-exhaustive list of example topics as well. ICES seeks to fund interdisciplinary work at one particular boundary between computer science and economics & social sciences. As always with anything new at NSF, there will be lots of questions. Email CISE/CCF Program Director Tracy Kimbrel (tkimbrel@nsf.gov), SBE/SES Program Director Nancy Lutz (nlutz@nsf.gov), CISE/IIS Program Director Sven Koenig (skoenig@nsf.gov), or CISE/CNS Program Director Darleen Fisher (dlfisher@nsf.gov) and we will do our best to answer the questions. If you're wondering Is my project suitable for ICES? be sure to include a one or two page description with your email because that will help us with the answer. The deadline for submitting proposals to ICES is October 5, 2010.

NEW math on Futurama

The Aug 19, 2010 episode of Futurama had NEW math in it! It also has some other math refs.

1. This website claims that Ken Keeler, one of the writers who has a PhD in math, devised a NEW theorem for use in the show. The theorem and proof are here. I do not know if it is new but it is correct and interesting.
2. Bender the robot had mind switched with Amy, so he was in a human body. In order to prove that he was really a robot he had to pass the reverse Turing Test.
3. Since PURE MATH lead to a solution of a PRACTICAL PROBLEM The professor exclaimed And they say pure math has no real applications!

This is the first time I know of where some new correct math was introduced on a fictional TV show. NUMB3RS often had new bogus math.

Both The Simpsons and Futurama have websites devoted to math refs in the show: Simpsons Math, Futurama Math.

It is not surprising that The Simpsons and Futurama have math refs since writers Jeff Westbrook, David X. Cohen, and Ken Keeler who write for these shows, are all math folk.

See these two prior posts for more on comedy and math.

Is Scheduling a Solved Problem? (Guest Post)

(Guest Post by Ben Fulton.)

"At first glance, scheduling does not seem like a topic that requires much attention from computer scientists".

This was how I wanted to start my review of a book on scheduling, but Bill Gasarch called me out on it.  "Really?" he said.  "I don't know any computer scientists who think scheduling isn't important."  It's true but computer scientists aren't the ones taking first glances at scheduling problems.

They're curriculum designers trying to determine which instructors are needed to teach all of the classes for the fall semester.  Shop managers wondering how the widgets could be sent through the assembly line more efficiently.  Kids on the playground choosing up sides for a soccer game (a problem identical to partitioning a set of jobs with known running times between two processors).   These are the people with scheduling problems.  They'll think about their problem for a few minutes, and come up with a good solution in each case.

The curriculum designer - possibly Michael Mitzenmacher  - might decide that the most important goal is to keep all instructors at around the same number of teaching hours.   In that case, each next available assignment would be given to the least busy instructor.   In doing so, he'll choose the List scheduling algorithm first proposed by Graham in 1966 and known to be no worse than twice as slow as an optimal schedule.

The kids will choose Greedy.  They'll choose a couple of captains and alternate picking the "best remaining" player, in the same way that a scheduler would choose the "largest remaining" job.   Greedy is a heuristic that runs in polynomial time.  It's not guaranteed to find the best solution it's The Easiest Hard Problem but the kids are interested in having competitive teams, not making sure that all possible sets of children can be perfectly divided in polynomial time.

The shop manager is likely to have a lot of different constraints to take into account, but she might notice that a station can stop working on one widget and start on another one, if the second is likely to be finished more quickly.  She probably won't realize it, but the Shortest Remaining Processing Time algorithm is known to optimize the average time to completion of the widgets.

In all three cases, the algorithms they choose are simple, easy to describe, and should work fairly well in their situations.  The schedulers aren't computer scientists - just people with problems to solve.   They'll take a first glance, and they'll solve them with a minimal amount of effort.  Even if you showed them a way to solve their problems that was twice as efficient, but also much more difficult to understand, they'd probably reject it.

So what's the point of studying scheduling?  The practical problems are solved. 

That's the first glance.  You've got to dig a little deeper to find the interesting problems in scheduling.  For example, the complexity of simply describing scheduling problems is a subject that hasn't fully been explored yet.  Problems are typically broken down three ways: the number of processors available; the constraints on when jobs can be run; and the criteria for determining whether one schedule is better than another.  Even if the first and third items are fairly simple, setting up a job precedence graph, lag times, and perhaps a few rules involving a specific processor needing to run a specific job, will likely generate a description so complex that an engineer trying to solve the problem might not even recognize it.

Scheduling gurus Anne Benoit, Loris Marchal, and Yves Robert also ask this question.  In response, they outline some areas of study involving distributed-memory parallel computing that could give rise to some interesting practical improvements. 

That's where you go when you're past the first glance.   And that's why computer scientists need to pay attention to scheduling.

 

Comments

Bill and I are strong believers in freedom of speech and have long since had an open comment policy, allowing anonymous comments, no moderation (except old posts for spam) and never deleting comments (again except for spam). This has allowed our blog to serve as a public forum for the community giving a place where people can express their opinions openly.

The level of nastiness has dramatically increased in the last couple of months, but we've maintained this policy believing everyone should be allowed to share their opinion, whether it be good, bad or ugly. But some seem to be purposely incendiary instead of giving a real point of view. Please keep comments civil and on topic so this blog can continue its long role where we can have fruitful discussions of the important issues and ideas in computational complexity and theoretical computer science.

NSF Updates

Many changes at the National Science Foundation both in programs and personnel. Some highlights of upcoming CISE programs.

• Expeditions is moving to an 18-month cycle but this year's preproposal deadline is September 10. Last year's awardees have yet to be announced. (Update: Just announced)
• The CCF Core (traditional theory grants) have three deadlines: September 15 (medium), November 28 (large) and December 17 (small).
• A new program Interface between Computer Science and Economics & Social Science (ICES), proposals due October 5. This program came out of a workshop held at Cornell last fall and its report.

Unlike conference deadlines, NSF and other grants change frequently. If you are a US academic you should subscribe to the CISE emails and RSS feeds (see here) or check the Theory Matters Funding Page often.

For personnel, let's work our way up. Richard Beigel, a theory program director, is finishing his term and heading back to Temple. There was a part-time replacement chosen but looks like that will be delayed. Might be a slower turn-around on theory grants this year. Tracy Kimbrel stays on as a program director.

Susanne Hambrusch will become the new director of CCF, the division of CISE that funds most of theory. Susanne replaces Sampath Kannan who is returning to Penn. 

The search for a new CISE head (called Assistant Director) to replace the already departed Jeannette Wing continues but no announcements yet.

MIT Engineering Dean Subra Suresh has been nominated by Obama for NSF Director and awaits congressional approval. 

The NSF budget process for next year looks good so far but there has been talk of a congressional freeze on most domestic activities. The NSF is preparing for both possibilities.

Spielman Receives the Nevanlinna Prize

Dan Spielman wins the Nevanlinna prize for "smoothed analysis of Linear Programming, algorithms for graph-based codes and applications of graph theory to Numerical Computing." Let's also not forget that as an undergrad Spielman co-authored one of my favorite complexity results, PP is Closed Under Intersection. A nice recognition for just a brilliant career.

Other IMU prizes awarded at the ICM opening ceremonies in Hyderabad, India: The Field medals go to Elon Lindenstrauss (Ergodic Theory), Ngô Bảo Châu (Algebraic Geometry), Stanislav Smirnov (Statistical Physics) and Cédric Villani (Mathematical Physics). The Gauss Prize goes to Yves Meyer (Number Theory) and the first Chern medal goes to Louis Nirenberg (Differential Equations).

Tim Gowers is blogging the meeting and the ICM is offering live streaming of the plenary sessions. The Nevanlinna Prize lecture will be given Saturday at 4:15 AM Eastern time. Also notable is Irit Dinur on PCPs at 12:45 AM Eastern Saturday morning.

Today is Paul Turan's 100th Birthday!

The following conversation is a fictional version of a real conversation.

Lance: Bill, Wed August 18, 2010 is Paul Turan's 100th birthday. We should post on it.

GASARCH: WOW, he's still alive? Will there be a conference in his honor? Will he go to it? Will he enjoy it? (ADDED LATER FOR CLARIFICATION: Noticing that Lance's mention of Paul Turan is actually a pointer to a Wikipedia Entry on him.) Lance, I see you have one of those gizmos that lets you insert pointers into your speech.

Lance: Uh, Paul Turan is dead, but if he were alive it would be his 100th birthday. And of course I have one of those gizmos--- I am a firstblocker

GASARCH: Even though he is dead can we still celebrate? Is there cake someplace? How about a free lunch?

Lance: No cake. And the economists I hang out with say there is no such thing as a free lunch. But we should post about it.

GASARCH: Okay. I know a nice proof of Turan's theorem and two applications, so I'll post about it.

When Lance first asked me to do this post my first reaction (after I found out there would be no cake or free lunch) was Paul Turan- Turan's theorem in graph theory. I know a nice proof of it that is not on Wikipedia. I also know two applications of Turan's theorem that I don't think are well known. I'll write those up as part of my post. (I will do this later in the post.) But then I looked at his Wikipedia Entry and I saw that he did so much more than graph theory. He also worked in Analysis, Number Theory, and Analytic Number Theory. Moreover, Wikipedia claims that Number Theory was his main interest. In addition he, along with Paul Erdos, made the Erdos-Turan Conjecture which has inspired so much later work (I will state it later.)

Is it good to have a theorem named after you? While we would mostly think YES, it may overshadow all of your other work in peoples memory of you. On the other hand, if it was not for Turan's theorem I would not know who he was and I doubt Lance would ask me to post on Turan's 100th birthday.

Is it good to have a conjecture named after you? It is so long as its open. Once someone proves it your name will vanish from the literature. Just ask Baudet or Vazsonyi (Baudet's conjecture is now van der Warden's theorem, and Vazsonyi's conjecture is now the Kruskal Tree Theorem.)

Turan's theorem:

If G is a graph with n vertices and e edges then G has an independent set of size at least n²/(2e+n)

Here is an application:

If S is any set of points in the unit disc (including the boundary) then there exist n²/6 - n/2 pairs of points such that each pair is of points that are ≤ sqrt(2) apart.

Here is my write up of a nice proof of both Turan's theorem and the application. The proof is from the Alon-Spencer book on Prob method. I do not know whose proof it is. (ADDED LATER: The proof is due to Ravi Boppana- see the comments.) I don't know where I read the application; however, it was by Paul Turan. If you know of other applications please leave comments about them.

Here is another application:

Assume you want to find the MAX of n elements and you get to ask k rounds of questions. It is know (without Turan's theorem) that you can do this with O(n^{(1+(1/(2k-1))}) questions-per-round. Using Turan's theorem you can show this is optimal. (The exponent is 1+(1/(2^k-1)) in case its hard to read.)

A write up of the case of k=2 is in the manuscript pointed to above. Once you read that you should be able to generalize it to k rounds easily.

The Erdos-Turan conjecture is the following:

Let A be a set of natural numbers. If Σ_{x ∈ A} 1/x diverges then A has arbitrarily long arithmetic sequences.

Some have suggested that this replace Poincare's conjecture on the list of Millennium prizes. See here for more on the conjecture.