Broader Impacts

Nicole Immorlica reports on the NSF CISE Broader Impacts Summit held last week in DC.

We've all seen it. Most of us have even written one. I'm talking about that ``clearly marked paragraph'' in the summary page of each and every NSF proposal:

Broader Impacts This proposal has far-reaching impacts. As part of my program, I will develop a new graduate course entitled My Research Area, that will introduce students to cutting-edge research in Proposal Topic X, Y, and Z. I will also incorporate these lectures into some of my Undergrad Courses. Special attention will be given to recruiting Women and Minorities. And I may even talk to A High School Student once in a while. Yada yada.

As often written, these broader impact sections, like the one above, read like the teaching section of my job description. So then, what is a broader impact, really? How can we improve our impact? And, most importantly, why should we, as a community, care?
I am now on an airplane returning from an NSF summit organized by Tracy Camp, Juan Gilbert, Judy Goldsmith and Samir Khuller (kudos to you) that discussed just that. The summit consisted of about 100 members of the CISE research community, and the purpose was to collect input from us about what we want broader impacts to be and how they should work. My working group was tasked with fleshing out Broader Impact #4, ``Broad Dissemination and ...'' (who knew, there are in fact five types of broader impacts, contained in a bulleted list in some NSF document from 2007, and yes, they all have long unmemorable bureaucratic names). Here's what we had to say (disclaimer: all comments are colored by my own personal biases and are not intended to accurately reflect the opinions of the participants etc. etc.):

1. What is a broader impact? All sorts of really cool things count here. In our group on broader dissemination, we came up with: blogging, YouTube video clips, maintaining wiki pages, writing a textbook, a popular science book, directing a play about science, designing a museum exhibit building computers with kids, with senior citizens, talking directly to the curious public in Scientific Cafe, with K-12 at National Lab Days, talking to the media, writing your representatives... Many of these have been done before, and I think there will be a link on the NSF website sometime soon giving pointers to some wonderful examples. More generally, a good broader impact is realistic and, ideally, measurable — points which ought to be discussed in the proposal.
2. How can we as a community help our individual members improve their impact? Some people have an internal fire that is fueled by helping others, and for those we can enable their impacts by simply making it easier to give. For this, the NSF will provide lists of ideas, and several programs like National Lab Days and BPC further help by providing ``match-making services'' that give a searchable interface to existing outreach opportunities (looking around there, I found a local high school that wants someone to come talk about careers in science, for example). Then there are also carrots and sticks. The carrots are higher weight for broader impacts in the review process as well as the tenure process (ummmm, I'll believe it when I see it); and the sticks are holding PIs accountable for their proposed impacts through annual reports alongside a threat of withheld funding upon failure to attempt said impacts (spank spank).
3. Why should we care? If you haven't figured it out by now, I am an incredibly cynical and suspicious individual. While I personally care about certain types of community service, I nonetheless felt that broader impacts in a proposal were simply a nod to Congress, a necessity that allows our elected representatives to justify giving us hundreds of millions of tax dollars, and of minimal importance in funding decisions and career success. I now see that, while there is a certain grain of truth in my snide remarks, the NSF is on a serious mission to change all this, and we should be too. We have a passion, and as privileged members of humanity, we have a duty to share our passion with those around us, thereby enriching their lives as ours were enriched for us by circumstance and chance and past generations of great givers.

The P vs NP quiz Show. NP! NP! NP!

Some random thoughts about quiz shows.

THOUGHT ONE: There could be a quiz show based on P and NP. We all think that FINDING an answer is harder than VERIFYING an answer. We use this! The contestant gets a question (or perhaps a category of questions) and is asked

P or NP ?

NP means that they will try to ANSWER the question. P means they will get to hear a POSSIBLE answer and VERIFY IT. NP is worth more money, perhaps alot more. How to verify?--- a few ways are possible.

1. The host gives the correct answer and the contestant either says (1) OH, I knew that- here is how I knew it (and then gives an explanation of how they knew that). Thus the contestant must verify that he can verify. If so, they get some money. If not then perhaps a bit penalty like lose ALL of their money or get an electric shock. (2) OH, I didn't know that. No money but no penalty.
2. Hook the contestant to a lie-detector and if they say claim Oh, I knew that and they are not lying then they get some money. If they claim they knew it and are lying then they are already set up to get an electric shock, so do that.

Get the audience to yell NP! NP! NP! --- rooting for the contestant to GO FOR THE BIG MONEY!

Could there be quiz shows based on other complexity classes?

THOUGHT TWO: On the show Cash Cab after contestants have finished they can either WALK AWAY (with money that is usually between 400 and 1500 dollars) or risk it on a DOUBLE OR NOTHING video bonus question. Should you risk it? There are two parameters X and Y.

1. If you didn't do that well, so you have LESS THAN X, then you are off your game and shouldn't risk it.
2. If you won a lot of money, at least Y, then you should just be happy and walk away with it.
3. If you won between X and Y then do the video bonus question.

I am risk averse, so X ≥ Y and I would never do the video bonus question. How about you? It might matter how much 400 or 1500 dollars is worth to you--- so you may very well be a risk taker in Cash Cab but not in Deal or No Deal where the amounts of money are much larger and thus more likely to be life changing. So X and Y might be functions of, not just how risk averse you are, but also on how much money is at stake. Could this be modeled?

THOUGHT THREE: When you watch a quiz show where there is only one contestant (e.g., Who wants to be a Millionaire or Cash Cab) and you yell out an answer, and the contestants yell a different answer, who do you hope is right?

1. I hope that they are right.
2. Almost everyone I've asked disagrees: That is, if I ask Alice, Alice hopes that Alice is right and the contestant is wrong.
3. If I was watching with someone I wanted to impress then I might hope that I am right.
4. If I like (dislike) the contestant then I hope they get it right (wrong) ind of what I yelled out.
5. So- what do you hope for, and why?

I expect to see a paper at INNOVATIONS on any or all of these topics.

The Lefthanded Latina Lesbians in Algebraic Topology Workshop

There was a Women in Theory Workshop at Princeton From June 19-23. ***SORELLE***, who was there, has some intelligent and interesting things to say about it here.. I will, instead, offer up a question.

I was at a Ramsey Theory Workshop in Italy and it was noted that of the 27 people there, none were women. Is there a shortage of Women in Ramsey Theory? Is this a problem? I suspect there is a shortage, however Ramsey Theory is too small an area to worry about it. Hence I doubt there will ever be a Women in Ramsey Theory Workshop.

Should there be a African-Americans in Theory Workshop? There are so few that it would end up being a bunch of non-African-Americans discussing why there so few African-Americans in Theory. To have a workshop analogous to the Women in Theory Workshop you need a larger critical mass. How many African-Americans are in Theory? What if I drop the requirement they must be American? I honestly don't know but I suspect its not that many. (If I am wrong then please let me know in the comments.)

Let A be an area (e.g, Recursive Algebraic Topology) and P be a subset of people (e.g., Left handed Latina Lesbians). When does a on P in A Workshop make sense? If A is too small then it would not make sense. If there are very few P's in A then there really can't be a such a workshop unless its mostly non-P's discussing why there are so few P's in A. If P is too big then there may not be a need for such a workshop; however, there may still be if there are issues facing P's that are not facing non-P's.

1. There have been African Americans in Mathematics Workshop. Here A is big enough and P is above critical mass.
2. According to this 24% of all lawyers are female and 44% of all law students are female. There may still be a need for workshops for female lawyers as they may face issues that male lawyers do not. Here was one: A Transformational Workshop for Women Lawyers.
3. Male Nurses are few in number, but there are some and I suspect they have problems that women nurses do not have. I do not know if they have workshops, but they do have their own magazine here.

What other workshops or conferences or whatnot on these types of issue have there been?

Most conferences hope that they will last a long time (e.g., We just had the 25th CCC. I hope there is a 50th). I suspect that the participants in the Women in Theory Workshop hope that these workshops are eventually not needed.

Talking about your work with a layperson

How to best describe what we do to the layperson? It depends on what you mean by layperson.

I was in Austin Texas visiting my nephew Jason. I was also giving a talk at the University. My nephew fixes forklifts for a living and does not care about abstract things. (I'd be as bad at his job as he would be at mine.) He asked me what the talk was on. I think he asked just to be polite but did not really care. Even so, I tried to put it in as concrete terms as possible. My thought process: (1) Don't use n. Use an actual number, say 100. (2) Don't state a theorem. State an easily grasped corollary.

BILL: Picture that there is a 100 by 100 chessboard. Picture that you want to put queens on the diagonal so that every square of the board is either covered or under attack. What is the least number of queens you need for this? (NOTE: I leave it to my readers to prove that, for an n x n chessboard, this is IDENTICAL to finding large 3-free sets, that is, large sets that do not have arithmetic progressions of length 3.)

JASON: That is the dumbest problem I ever heard!. First off, chess is played on an 8x8 board. Secondly, only once while playing chess did I ever get my pawn to the end of the board to get a second queen, never mind getting n-o(n) queens (he didn't put it that way). And thirdly... who cares?

BILL: I don't suppose it would help to tell you that this relates to some deep mathematics of interest.

JASON: Of interest to who?

BILL: Uh... Never mind. (I thought about telling him that better bounds on the VDW numbers could get you $3000 dollars but decided not to.)

I usually do better than this with very concrete easily grasped statements. But he doesn't care about this problem. And actually, why should he? (I am sure some of my readers don't care about this problem either.)

The Future of STOC

I set up a new blog, Future of STOC to discuss role of our main conference and how to achieve it.

At STOC this year we had a relatively large attendance of 350 but why not 1000 or more? Why isn't our flagship conference bringing the theoretical computer science community together?

A couple of months ago I wrote up a proposal to address these issues and circulated them to a number of people in our community. You can read the proposal and the responses on the blog. Based on those responses the SIGACT Executive Committee decided to slowly increase the maximum number of acceptances but also open up the discussion at the STOC business meeting, which we did. Many people at STOC asked me to post the proposal and the responses and open up the discussion to the broader community. That's the purpose of the new blog.

We want to hear from you, the theory community. Tell us if you love STOC the way it is. Or how can we change STOC to make it more relevant to you? Even if you would never plan to come to STOC, tell us why.

Go to the Future of STOC and join the conversation.

Foundational ... or simply a curiosity (Guest Post by Vijay Vazirani)

(Guest Post by Vijay Vazirani)

Foundational ... or Simply a Curiosity?

Conventional wisdom has it that whereas linear programs have rational solutions, nonlinear programs have irrational ones. The discovery, in recent years, of increasing numbers of nonlinear convex programs that always admit rational solutions is challenging this long-held viewpoint. Furthermore, these convex programs capture the solutions to some fundamental problems in mathematical economics and game theory, e.g., market equilibrium under linear utilities.

As if that were not enough, these convex programs also admit combinatorial polynomial time algorithms for computing their (exact) optimal solutions; very recently, even strongly polynomial algorithms have been found. I am writing this guest post at the suggestion of several people who were not aware of these developments.

The main question that arises is: Is this phenomenon simply a curiosity or is it indicative of a grand, new chapter in the theory of algorithms? Let me put forth some reasons to believe that the latter may be the case.

Most of us are familiar with the notion of integral LP's -- LP's that behave like integer programs, in that they always admit integral optimal solutions -- and the key role they played in the birth and blossoming of combinatorial optimization. Indeed, some of the most elegant and foundational algorithms (e.g., for matching and max-flow) and algorithmic ideas (including the notion of polynomial time solvability) were discovered within this field.

Of course, not every combinatorial optimization problem admits such an LP; in particular, none of the NP-hard ones do. The latter were tackled via LP's that admit near-optimal integral solutions; their study lies at the core of the field of approximation algorithms. Again, it is remarkable that for many fundamental problems, their hardness of approximation is captured exactly as the integrality gap of such an LP (or SDP).

In view of this larger picture, and the clean, canonical and elaborate structure that was exploited in obtaining the combinatorial algorithms, the discovery of rational convex programs seems more than a curiosity, though only time will tell. However, rational convex programs are not likely to be found for more than a couple of handfuls of problems, as was the case for integral LP's. If so, where does this take us?

My best guess at present is that we need to seek combinatorial algorithms for finding near-optimal rational solutions to nonlinear convex programs; the motivation being that as always, we expect such algorithms to yield a wealth of valuable insights. In the past, such insights were crucially used for advancing the theories mentioned above. Once again, only time will tell if this is the right way of building on rational convex programs -- and of course, we should not forget that mathematics has its own agenda and its own ways of throwing surprises at us!

For further information, please see the introduction to the following paper here and references mentioned therein; the latter are available on authors' web sites.

CCC 2010

( Reminder:Deadline for submitting to special issue of Theory of Computing in honor of Rajeev Motwani is July 30. See here. )

CCC 2010!

1. Ran Raz gave an AWESOME invited talk on Parallel Repetition of two player games ( here are the slides). What was most striking to me is that this line of research lead to the solution of a math problem (the Foam Problem) which would seem to be completely unrelated to it. Has this happened before- research starting in TCS leads to the solution of a seemingly unrelated math problem? Of course, my question is ill defined since TCS, Math Problem and seemingly unrelated are not well defined.
2. The talks following Ran's were also on two player games so his talk was a great way to get you up to speed on what follows. I would recommend that the Program Committee try to do this in the future: have the invited talk be the first in a session on related material. (I also realize that this may be hard to pull off.)
3. Subhash Khot gave a good invited talk on The Unique Game Conjecture. (These Slides should soon be available soon on his website. There is already a written survey on the material on his website and also slides he gave at FOCS05 on UGC. Here is his webpage.) This conjecture has been a great breakthrough in that it gives us something reasonable to assume that gives approx lower bounds- some of which match the approx upper bounds. It has also had many other applications unforeseen even by Khot when he first conjectured it. (Over dinner Khot told me he is only 90% sure that it is true. Gee, I thought he would have more confidence than that!.)
4. The talks that followed Khot's talk were all on UGC, and that was a big win.
5. Oded Regev gave great invited talk on The Learning with Errors Problem. (Talk and paper are here.) This was a talk where I learned about a problem I had not heard of and its connections to other problems. One of the applications was crypto (not surprising- that is Regev's main area.) The talks that followed it did not connect to it as much as for the other invited talks. This does not take away from the fact that I learned stuff of interest that I did not know ANYTHING about before.
6. Jakob Nordstrom gave a nice talk On the relative strength of pebbling and resolution. I had not known that pebbling was used to give lower bounds on resolution and I look forward to reading his 200 page survey on this topic. (It is on his website.)
7. Eric Allender had a paper in the first CCC (called STRUCTURES then) on Auxiliary PDA's. Eric Allender had a paper in the 25th CCC on Auxiliary PDA's. An Auxiliary PDA is a PDA with an additional log space workspace. I look forward to an Eric Allender paper on Aux PDA's at the 50th CCC. Note that Eric has worked on many other things as well.
8. Hrbues, Wigderson, Yehudayoff had a paper on Relationless Completeness and Separations. The idea here is to take algebraic complexity and see if you can get lower bounds if you do not assume that the operations are associative or commutative. The good news is that they did! The bad news is that the bounds for the case where the operations are associative and communicative are as hard as they were when Valiant first proposed this model many years ago. Valiant was at the talk and told me later that he would have thought that there would be more progress by now.
9. Alexandra Kolla had a paper Spectral Algorithms for Unique games. She seems to think that the UGC is false!
10. Impagliazzo and Williams talk on Communication Complexity with Synchronized clocks was an interesting new model of Communication Complexity which was used to solve some problems in classical CC. Also easy to understand since it was the first talk on a model. I suspect that within 5 years people will be using hard math to study this model and the talks will be harder to follow.
11. Buhrman, Fortnow, Koucky, Loff's paper show us that random strings are powerful in Derandomization from Random Strings
12. The most depressing talk was Derandomizing Arthur-Merlin Games and approximate counting problems since it seemed to imply that we need lower bounds on circuits to get derandomization. Worth knowing but not good news.
13. Business Meetings and Spouses: I know of three people who brought their non-complexity spouses with them to Boston. (They went sightseeing during the conference.) There are three approaches to what to do the night of the business meeting. One went to the meeting and left the spouse at the Hotel. One skipped the meeting to be with their spouse. One brought the spouse to the meeting. What would you do?
14. Business meeting was uneventful. CCC11 will be in San Jose as part of FCRC, CCC12 will be in Portugal (this was already sort-of known). Next year we may be leaving the 10th century and rather than give out handwritten proceedings on parchment we will be doing something electronic. Valentine Kabanets and Dieter von Melkebeek will be on the CCC steering committee, replacing two people whose terms have expired.

László Lovász wins Kyoto Prize

László Lovász wins the Kyoto Prize for "Outstanding Contributions to Mathematical Sciences Based on Discrete Optimization Algorithms."

Alternative Careers for Logicians

(Will post on Complexity next week. I am waiting until the invited talks have their slides online so that I can point to them.)

Let's say you just got a PhD in Logic. (ASIDE- my spell check program flagged PhD, but it gets 54,000,000 hits on Google so it has to be correct.) The job market is not so good. That is, the academic job market is not so good. I have recently been alerted to two alternative career paths one could take.

1. Get a job on Wall Street! You are probably thinking Oh, they want people that are good at math and can program. While that is true, they actually want people who know about ordinals! Ordinals? Yes Ordinals! See here.
2. Peter Cholak is a logician at Notre Dame who has had seven PhD students finish. Two of them went then went to Catholic seminary and become Catholic priests.

What to make of this? In American there is a priest shortage (see here for an article about it that mentions the law of large numbers). Hence the priesthood is a good job market. Are there other logicians-turned-priests? In this day and age I suspect there are not that many. In an earlier time when neither field required the kind of training they do now, there may have been more.

The job market for Protestant Ministers and Rabbis is not very good (See Protestant Ministers and Rabbis.) I was unable to find out how the job market is for Imam's.

I suspect that the decision to go into any of these fields is more of a calling than having a keen eye on the job market. Peter Cholak's two logician-turned-priest students just got their calling a bit late. They were both at the Fifth Conference on Logic, Computability, and Randomness so they are both trying to keep up some with logic. That may be hard; however, they may have help from up above.

News from Cambridge

Now that teaching has ended I plan to focus again on my P v NP book. I won't go on a full blog sabbatical, instead I'll aim to post once a week as well as keep up my tweets.

As you readers know, STOC, Complexity and EC all met last week in Cambridge, Mass. Complexity closed its registration at 140, EC broke 200 and STOC had about 350, high numbers for those conferences helped by both location and co-location. All three conferences will be part of FCRC in San Jose next year. Salil Vadhan will be PC Chair for STOC, Omer Reingold for Complexity. STOC 2012 will be held in New York City, CCC 2012 in Porto, Portugal home of Port Wine and my favorite delicacy. EC doesn't think that far ahead. 

The 2010 Gödel Prize will be awarded at ICALP to Sanjeev Arora and Joseph S.B. Mitchell for their concurrent discovery of a polynomial-time approximation scheme (PTAS) for the Euclidean Travelling Salesman Problem. 

The STOC proceedings are on-line including best student paper and best papers. The EC proceedings is also on-line with their best paper and no best student paper this year. The Complexity proceedings (published by IEEE) not on-line yet but the best student paper was The Gaussian surface area and noise sensitivity of degree-d polynomial threshold functions by Daniel Kane of Harvard. CCC didn't pick any best paper winners.

The TCS Visions are now on the CCC site, and in many more formats on Theory Mattters. Please feel free to make use of these slides to sell theory to chairs, deans, students and the general public.

At the STOC business meeting I talked about addressing the problem that STOC still only attracts a small fraction of the theory community. More on that in future posts.

Michael Schapira has a nice guest post on the EC conference and Muthu on the EC workshops. Bill promises a post on CCC tomorrow and we may have some vidcasts for you in the future.

Having CCC and EC overlap made it difficult to be a close part of either meeting. I can't believe I skipped the EC Google-subsidized Charles River Lobster Dinner cruise for the CCC business meeting but at least I got some Facebook jelly beans. I also got the HiPPo below from Ronny Kohavi's invited EC talk. The EXP stands for experiments that one should use to make choices instead of the HiPPo (Highest Paid Person's Opinion). But EXP is also a complexity class and so the hippo captures both meetings for me.

Another post on Martin Gardner

(I will post about CCC 2010 later in the week.)

Several people have posted on the death of Martin Gardner:

1. Complexity Blog (Lance)
2. Shtetl Optimized (Scott).
3. Ars Mathematics

I did not because of travels, but now I can. (Full Disclosure- This Blog is part of the Scientific American Partner Network. Martin Gardner had a column in SA for many years.)

About a year and a half ago I reviewed some books of Martin Gardner for my SIGACT NEWS Book Review Column. (The review is in this column.) Before I send in a review I contact all of the authors of books, authors of reviews, and editors of the books and send them a copy of the review (by email). I was told that Martin Gardner didn't use email (he was 94 years old!). So I sent him the review by postal mail (you can ask your grandfather what that was).

I got a response! I posted it here though I blocked out his address and phone number for privacy reasons. As you can see the letter is coherent and cogent (I've gotten less coherent letters from people half his age). It is good to know that he was sharp till the end.

The first theorem I ever read on my own was in one of his books: it was that (in today's terms) a graph is Eulerian iff every vertex has even degree. (ADDED LATER: The correct theorem is that a graph is Eulerian (has a cycle that hits every edge exactly once) iff it is connected and every vertex has even degree.) I also learned about The Unexpected Hanging from one of his columns. These two stand out the most; however, I learned A LOT from his columns, plus I learned that there was more to math than what was taught in the classroom.

Whats your Game Mr. Bond- The sequel!

(I will post about CCC 2010 later in the week.)

The word Game is used in many different contexts within math and computer science. I list out all that a group of us at last years Dagstuhl thought of:

1. Duplicator-Spoiler Games are used in Descriptive Complexity theory and Logic. They are also called Ehrenfeucht-Fraisse games. (The pointer, a Wikipedia entry, has a pointer to EXCELLENT slides on these games.) Example result: wellfoundness for linear orders is not first order definable.
2. Every A &sub {0,1}^&omega gives rise to the following game: Alice picks c₁ &isin {0,1} Bob picks c₂ &isin {0,1} Alice picks c₃ &isin {0,1} Bob picks c₄ &isin {0,1} etc. If c₁c₂c₃ ... is in A then Alice wins. If not then Bob wins. The Axiom of Determinacy states that, for every A, one of the two players has a winning strategy. This has been proven for Borel sets A. Full AD contradicts Full AC. See here. I have posted on it before here.
3. Banach Games. Let A be a subset of R. All numbers picked are in R. Alice picks x₁. Bob picks x₂ < x₁. Alice picks x₃ < x₂. Bob picks x₄ < x₃. etc. If &sum x_i &isin A then Alice wins, otherwise Bob Wins. For more on these see here.
4. Banach Mazur Games. (I am not quite sure of this one since I could not find stuff on the web and it looks too much like the games for AD. If this is incorrect please comment.) Similar to the games under AD; however, instead of picking an element of {0,1} the players pick an element of {0,1}₊. This has been used to define when a set is meager and has been extended to poly-time settings. Also has been extended to graphs: see here
5. Martingales. Let A &sub {0,1}^&omega. x is in A, but the player does not know what it is. The player starts out with one dollar (wow!). When the player sees the first n bits of x he bids on the (n+1)st bit. Can he win? Depends on A. Has been used to define measure 0 and has been adapted to the poly time setting. Jack Lutz has worked a lot on this stuff.
6. Complexity Classes have been defined via games. Usually a prover wins if he can convince a verifier that x &isin A. Many parameters can be changed to get many classes (number of rounds, number of provers, strength of verifier, strength of prover(s), prob of error allowed). I would include the Unique Game Conjecture in this use of the word game.
7. Pebble Games have been used to get time-space trade offs on simple models of computation. More recently they have been used to get lower bounds on resolution theorem provers. For a survey see the first paper on this page. Warning- the survey is 200 pages!
8. Games have been used to prove theories decidable. Originally S2S (Second order theory with two successors, essentially the theory of infinite strings of 0's and 1's) was proven decidable by Michael Rabin. Later Gurevich and Harrington had a simpler proof using games. See this paper. Another excellent article on this, which alas is not on line, is Infinite Games played on Finite Graphs by Robert McNaughton, Annals of Pure and Applied logic, Volume 65, Issue 2, Pages 149-184.
9. Combinatorial Games like NIM have been well studied.
10. Game Theory needs no commentary here.
11. Richman Games are a way to combine Combinatorial Games with Game Theory. See this paper.
12. In adversary arguments in lower bounds we picture an adversary who is playing a game with the algorithm or with any possible algorithms.
13. Communication Complexity Games. Not sure these are really games, but the term is used.
14. Surreal numbers are actually games. See Conways book On Numbers and Games.
15. A lot of computer science and graphics go into video games.
16. There has been some study of strategies on real games like monopoly and chess. I gave one classification of games in this post. Note that GO and Chess are EXPTIME complete.

Note that most of these games are not fun.

Sims Complexity

I called home last night and my daughter Molly had an exciting story to tell. She was at her friend Danielle's house (the same Molly and Danielle from the video) and playing the Sims, a computer role-playing game.

One of the characters was using a computer which had an item "Solve the Unsolvable". Danielle clicked the phrase. A few minutes later a pop-up opens and says "Your Sim has made progress on the P = NP Problem".

Nothing like a video game to impress the little one.

STOC and EC and Complexity, Oh My

Tomorrow I'm off to Cambridge, MA for the 42nd Symposium on the Theory of Computing (STOC), the 25th Conference on Computational Complexity (CCC) and the 11th Conference on Electronic Commerce (EC). Looking like a big crowd. The hotels are full. There are more STOC tutorial registrants than seats in the tutorial room. CCC is threatening to cut off registration. Too many people is a good thing. We'll always find a way to squeeze people in.

These are the three summer conferences I go to regularly so I am registering and attending all three (anyone else?), even if it means racing back and forth across Oxford Street to catch people and talks at both the EC and CCC conferences. Bill will also be at STOC and Complexity. If you see us say hi.

These conferences also mark the beginning of summer for me as we just finished up spring quarter classes at Northwestern. 

Blogging will be light next week. Obviously a busy time and Bill never posts when traveling. I'll give updates via Twitter but don't expect live tweets from the STOC business meeting as I'm the MC this year. I'll do my best to keep it lively.

We do this all again next year as all three conferences are part of the FCRC meeting in San Jose.

Conference Acceptance Rates

In the latest CACM, Jilin Chen and Joseph Konstan analyze data from the ACM DL and conclude that low-acceptance rate conference have papers with higher impact (more citations). This shouldn't be too surprising. If Joe believes a conference A bestows more prestige on their paper than conference B, Joe might submit his paper to A instead of B if it Joe's paper had a higher probability of being accepted into conference B. So in equilibrium conferences with higher prestige papers should have a lower acceptance rate.

Chen and Konstan suggest that conferences could lower than acceptance rate to get higher prestige. I have two problems with that advice. First of course my general annoyance of treating CS conferences as "journals that happen be be held at a hotel". 

Chen and Konstan have the causation effect backwards. Prestigious conferences do have a lower acceptance rate with other factors kept the same. But you can't necessarily up the prestige by changing the acceptance rate. The one decision the PC can make is how many papers get accepted into the conference. But accept fewer papers and in the future less people will submit their papers since they no longer believe they have a decent chance of seeing their papers accepted. it's possible in the long run to increase the acceptance rate while lowering the number of papers accepted.

When STOC moved to double sessions and accepted more papers, did the acceptance rate dramatically go up? No, because we had more submissions to match. But why does STOC have a higher acceptance rate than similarly rated conferences in other subfields? Theoretical work by its nature is easier to self-judge and most people whose papers are well below the accept/reject border of quality don't bother to submit to STOC.

You have a prestigious conference by the people that come. You can't engineer prestige, it has to be nourished.

Advice for an Engineer

A reader from Mexico asks 

I am a near-to-be graduate student from Computational Engineering. However, it wasn't what I expected from my career. I want to be a mathematician.

Computational complexity seems incredibly interesting, and I really want to take part in this amazing field. But because I'm an engineer I lack the basics to do any formal or proper research. I feel like I made the wrong career decision, even though I'm not bad at it and have a good job.

So, even though I'm behind on the math schedule, I really want to participate on some form of research. I'm unsure on how to proceed, though. I'm not versed enough in Math to be of real use and I don't feel like going back to school just yet.

What would you recommend on my position?

There are a number of computer scientists and even complexity theorists who started out in "the real world," realized it didn't feel fulfilling and went back to graduate school and on to successful research careers. It's not an easy road but it can be done.

If you are not ready or able to go back to school right away you should start exploring complexity on its own. Start reading a textbook (like Arora-Barak), read some lecture notes and when you are ready, try reading some of the latest papers in the field on ECCC and ArXiv and try to tackle some of their open questions. If it still excites you definitely consider graduate school. Worst case you'll end up back in industry and twenty years from now you don't want to regret choices not made today.

Avner Magen (1968-2010)

Toronto Professor Avner Magen died in a climbing accident on Saturday. He's had a number of important results on a variety of algorithmic topics.

Avner was one of our postdocs at NEC and we were co-authors on a SODA paper. He was a good friend and colleague and he will be sorely missed.

The department set up a memorial site where you can read memories of Avner and add your own.