Conventional Wisdom

Richard Lipton has a relatively new weblog. Quite a few provocative posts, particularly on the following theme.

Hopefully, these posts will raise issues about conventional wisdom, and these issues will cause you to re-examine whether or not “obviously” P≠NP. 

Lipton even suggests we should have a stimulus package for P = NP.

I would like to suggest that the government (NSF?) should fund a major project on P=NP, with the goal of accelerating the discovery of a solution. 

I agree with Lipton on the importance of the P v. NP problem, but I am a strong believer of the conventional wisdom. Just because many people believe in something that doesn't mean you should doubt it.

But my main concern is that the most likely outcome of such a project would be no significant progress towards settling the P v. NP problem in either direction, potentially making some proclaim the project a "failure". We have a theory-friendly NSF now but that won't last forever and I would hate to hand future NSF leaders any ammunition against theory funding.

Losing touch naturally was a good thing. Now...

I have received the following legit email several times (paraphrased):

`Hi, I am NAME (A NAME I DO recognize from my past). Are you the same Bill Gasarch who when TRUE FACT ABOUT ME (e.g., `Went to John Dewey High School in the late 70's')

This often resuls in a short email conversation along the lines of What are you doing now?

The notion of trying to reconnect with a long-lost friend may be an alien notion to todays high school kids. They never lose the connection. Its easy to keep up with friends even when they go off to different colleges, and beyond. This sounds like a nightmare--- how do you keep up with all of those people? We are losing a way to drop people out of our lives naturally. Will this result in too many friends? Less really close friends? With Facebook (and other means) you can have 1000 people you call friends. Are they friends? I honestly do not know. I thought the term efriend would catch on but it has not.

On a related note--- how does the witness protection program deal with this issue? I can picture a witness's child refusing to give up their facebook account. Or starting a new one and being spotted.

Then again, you can defriend someone on facebook. Technology has settled an old open problem of Jerry Seinfelds: How can you break off a friendship.

Proof-Ready Projects

The Guardian has an article about the beauty of algorithms which credits mathematicians as the developer of algorithms (as opposed to computer scientists). Don't feel too much envy for the mathematicians, as Wired blames a mathematician for the financial crisis.

Yesterday's Science Times has two articles on the Obama administration and science. John Tierney writes about how scientists do not always frame science policy issues well. Gardiner Harris and Kenneth Chang write about the immediate needs for the science money in the stimulus bill.

"It would be the height of embarrassment," Acting NIH Director Raynard Kington said, "if we give these grants and find out that institutions are not spending them to hire people and make purchases and advance the science the way they’re designed to do."

No problem says Harris and Chang, universities have plenty of "beaker-ready" projects ready to go.

For those who don't follow Scott's blog, check out the Globe article quoting him and Arora on computational intractability.

The FOCS Call

The 2009 FOCS Call for Papers has a few changes from previous calls.

"Optimization" is added to the list of topics.

The 2009 Call requires full proofs in the papers with no promise those proofs will be looked at.

Authors are expected to include full proofs of the central claims in the paper. If necessary, these proofs may appear in a clearly marked appendix. However, any material not included in the body may be ignored at the discretion of the Program Committee.

I have nothing against full proofs but I hope authors still worry more about giving the right intuition in their submissions than about dotting every i.

The Call also asks for a brief description due a week after the submission deadline.

The brief description should be no more than two pages, using the same font size, margins and spacing as the extended abstract. It should contain an informal description of the paper. It may contain an overview of the main results, concepts, or ideas introduced in the paper. It should provide the same understanding conveyed in a brief conversation or presentation. It may replicate material from the extended abstract, or even be a copy of its first two pages. But, it must not contain any technical material not present in the extended abstract.

This one puzzled me so I asked Dan about it.

It will have a few uses:

1. To make it easier for us to get more opinions about the contribution of a paper.
2. To make it easy for committee members to get a feel for papers they have not been assigned.
3. Ideally, to reveal the essence of a paper, unencumbered by the need for formal presentation.

We will soon produce and post examples of what we have in mind.

So the Call asks for both details and essence. Interesting.

Seeking the NON-Elementary proof of...

Consider the following:

Canonical VDW thm: For any k &isin N, for any coloring of N with an infinite number of colors, either

1. there exists an arithmetic progression of length k where all of the elements are the SAME color, or (e.g, if k=5, 10 RED, 14 RED, 18 RED, 22 RED, 26 RED).
2. there exists an arithmetic progression of length k where all of the elements are different colors (e.g, if k=5, 10 RED, 14 BLUE, 18 GREEN, 22 YELLOW, 26 PURPLE).

Henceforth I will refer to this as CVDW.

Recall

Szemeredi's Thm: Let k &isin N. If A &sube N has positive upper density (liminf_{n &rarr &infin} |A &cap {1,...,n}|/n > 0) then A has an arithmetic sequence of length k.

(Henceforth SZ) I have seen the following statement in two papers and one book (I'll paraphrase.)

It is easy to see that SZ implies CVDW.

1. I was unable to prove this. If someone out there can supply the easy proof please do so in the comments (my curiosity is far bigger than my ego).
2. The first step of the proof is obvious: if some color has positive density then we are done. So assume that they all have 0 density. The seconds step MIGHT be to take the set

   { x | COL(x) ¬in {COL(1),...,COL(x-1)}

   and show that it has positive density. But I don't know how to prove that, or if its even true.
3. If I assume that each color appears finitely often then I can prove there is a colorful k-AP using VDW thm. (I leave this to the reader.)
4. There is an elementary proof by Promel and Rodl. (An elementary proof of the canonizing version of Gallai-Witt's thm, Journal of Combinatorial Theory A, Volume 42, Pages 144-149, 1986. I have not been able to find it online, so if someone knows an online version let me know.) They actually show (as the title indicates) an elementary proof of the Canonical Gallai-Witt thm (multidim VDW), which I won't go into here. I have written up just the elementary proof of CVDW here: writeup.

LATE EDIT (Feb 26, 2009): One of my readers send me an ONLINE version of the paper. It is now at originalpaper.

The New Facebook Generation

[Dan Spielman has posted the call for papers for the 50th(!) FOCS conference. Submission deadline is April 2. The conference itself runs October 24-27 in Atlanta.]

No surpise my 13-year old daughter has started an active Facebook life. But my wife? Apparently the suburban mother generation has discovered Facebook, posting pictures, obsessing about the status message, posting trivia about their lives. My wife's old boyfriends have tracked her down. Luckily they are all either married or gay.

But I still don't get it, why do people want to follow other's lives so closely via Facebook and Twitter? I also worry about the time sink if I were to dive in.

A few months ago I took my daughter and her friends to the movies buying tickets ahead of time on Fandago. So on my Facebook page pops up "Lance has bought tickets to High School Musical 3". Thanks Facebook!

Movie Mistakes- or are they?

Note the following two movies mistakes. Or are they mistakes?

1. In The Wizard of Oz when the Scarecrow gets his diploma (instead of a brain) he says the following:

   The sum of the square roots of any two sides of an isosceles triangle is equal to the square root of the remaining side.

   This is incorrect. I suspect my readers spotted this mistake while watching the movie. If you type

   "Wizard of Oz" isosceles

   into google you get over 2500 hits-- far less than I would have thought. (Though if you replace isosceles with pythagorean you get over 8000 hits.) So this error is somewhat known. But is it an error? Possibilities:
   1. The writers and everyone who proofread the script did not catch this. Realize that this is not hard math. Wouldn't someone have noticed it?
   2. One of the points of the movie is that the Scarecrow is already smart. Hence the writers are trying to show that he was smart (though didn't know math) both before and after getting the diploma, so the diploma didn't change anything except his confidence. And when it comes to math, a misplaced confidence.
   3. Recall that the movie is all Dorothy's dream. The writers were making the point that Dorothy didn't know the proper way to state the theorem.
2. In Miracle on 34th street (1947 version) Kris Kringle, who claims to be Santa Claus, states that he has passed psychological tests, and brags that he knows that

   John Quincy Adams' vice president was Daniel Tompkins.

   But this is incorrect! John Quincy Adams's VP was John Calhoun! (Tompkins was James Monroe's VP.) How well known is this error? If you type

   "Miracle on 34th street" Tompkins

   into google you get over 1000 hits (far more than I would have thought). Is this really an error?
   1. Daniel Tompkins was our 6th VP. John Quincy Adams was our 6th Prez. They just didn't line up (see chart at the end of the answers to my prez quiz). Hence it was an honest mistake on the part of the writers (I find this far more believable than the Scarecrow-math error not being detected.)
   2. The writers were trying to tell us that Kris Kringle wasn't Santa Claus. Or at least put some doubt in our minds. Of course, that would only work if the audience knew their vice presidents. (Easy now with the excellent book Bland Ambition: From Adams to Quayle-- The Cranks, Criminals, Tax Cheats, and Golfers who made it to Vice President but harder in 1947 when the movie was made.
   3. There have been two remakes of the movie (that I know of) but I don't know if they contain the error. If you know, let me know.

A Great way to use a math blog

Timothy Gowers has suggested a line of research about the Density version of the Hales-Jewitt Theorem.. What is remarkable about what he proposes is that he wants a massive collaborative effort on it, as suggested in this blog entry of his. He has some other entries before that one ABOUT the notion of mass collaboration. Terry Tao has a companion post setting up a reading seminar on the density HJ theorem.

1. Both the collaboration and the reading seminar are great ways to use the Internet and their blogs! I often learn factoids or references from blogs. By contrast this gives people a chance to learn something deeper.
2. For LEARNING this is clearly a good idea that should work (if not for me then for others).
3. For PRODUCING new ideas I'll be curious how it goes. How productive does a research group get if it gets too big? At one point is there just too much noise? Then again, how many people are interested in this problem and this form of collaboration (I honestly do not know). Is not meeting face-to-face a problem?
4. Is this material important for TCS? Luca has a blog entry on the unreasonable effectivness of addive combinatorics in computer science, so that would be a YES.
5. Clearly I wish them well.

Sloan Fellows

The Sloan Foundation took out a full page ad in the New York Times today to announce the new Sloan Fellows. Many from our community on that page:

• Scott Aaronson
• Shuchi Chawla
• David Kempe
• James Lee
• Kamesh Munagala
• Ryan O'Donnell
• Luis von Ahn

Congratulations to all!

The Office

Suppose you had no specific reason to be on campus. No classes, no talks, no scheduled meetings with students/advisors, no meetings scheduled. Would you go to campus that day?

Not that long ago the answer would be of course you would. Maybe you might need to read a paper in a proceedings in your office or a journal in the library. You might have to have a short conversation with a colleague. You would need the computer (or secretary) at work to type up your paper.

Of course all of these activities can now be done electronically. Most of the time we spend at work gets spent on the same Internet we have access to at home or in the coffee shop. So why go to work?

We miss those random meetings. The people we bump into in the hallways. The tangents we have in lunch time discussions. Sometimes these meetings turn into important research projects or grant proposals. But more importantly they bring a sense of community. Often we get ourselves less attached to our departments, our colleagues and universities as we used to.

I'm not the first to say it, but as we get more connected we get more isolated. Technology will continue to push us in this direction: Who knows when we will all will take, if not teach, our courses on-line. Just remember you can't network if you are an isolated node.

STOC Papers

Last reminder: Complexity submission deadline tonight midnight Eastern.

In a nice move, Mitzenmacher posted both the titles and abstracts of STOC papers on the STOC website. Lots of strong papers, of course. Here are some that interest me for various selfish reasons.

• Exact Learning of Random DNF Formulas Under the Uniform Distribution by Linda Sellie. Linda was one of my first students at Chicago when I first started there in the late 80's but she had to leave graduate school early. But eventually she came back, kept working and received her Ph.D. from U. Chicago last spring under Stuart Kurtz with a thesis based on this nice learning result.
• An Axiomatic Approach to Algebrization by Russell Impagliazzo, Valentine Kabanets and Antonina Kolokolova. I like oracle results. I also like meta-oracle results. But especially I like meta-oracle results that generalize my meta-oracle results.
• A constructive proof of the Lovász Local Lemma by Robin Moser. The Lovász Local Lemma is a neat theorem that says if you have k events each occuring with probability p such that each event is independent of all but d other events than there is a positive probility that none of the events occur if ep(d+1)≤1 (no k in formula). Looks like Moser has a strong constructive proof. Alas while I like the Lemma, I never seem to have the right independence requirements whenever I want to use it.

Baseball Families and Math Families

(This article had help from Clyde Kruskal, Joe Kruskal, Bill Kahn, Hans Courant, and Lucy Moser.)

Bill James, the baseball statistician, once had an article on measuring Baseball Families. Who was the best baseball family? Would it be ...

1. The Alous: Felipe, Jesus, Matty were brothers. Moses was Felipe's son. All made the major leagues, and some of them were pretty good.
2. The Bonds: Bobby and Barry Bonds. Father/Son- both excellent. While you might rather have them then the four Alou's on your team, having four in a family just seems like a stronger family.
3. The Aarons: Hank and Tommie Aaron. Hank was a great player who hit 755 home runs (without steroids). Tommie, his brother, had a very short career. Even though its a real family, still doesn't seem like the right answer.
4. Babe Ruth alone: Bill James him rates as the best player of all time. Hence the "Ruth family" would seem to be a very good baseball family.

So, how to go about the question of who is the best baseball family ever? First we need a way to assign to a player some number saying how good he is. Bill James has already done this via a method called win shares. The idea is that you assign to a player how much he helped the team win. This is very complicated and I won't explain it here. However I will point out that it can't be negative and it varies quite a bit. For example Hank Aaron had 643 win shares, while his brother Tommie had 15. For some examples of players with high win shares see this.
So, you could just take the sum of the family members win shares. But this makes the family of one, the winner. We want a real family to get some credit for being a real family. Bill James' solution: Say the best person has a₁ win shares, the second a₂, etc. a₁ > a₂ > ... > a_n. Rate the family via a₁ + 2a₂ + ... + na_n. Under this metric the Alou brothers were the best baseball family as of 2003. See here for the numbers.

But I am still bothered. Why the combination a₁ + 2a₂ + ... + na_n? Is there some other way that is more mathematically sound or that can be derived? I doubt it since the question is somewhat subjective.

Clyde Kruskal has brought up another point. What if you had a longer link between relatives? What if you had a great-grandfather, grandfather, father, son. If the father is the best baseball player, start there. People who share half his genes (son and grandfather) count fully. But the great-grandfather counts less. You could even do this if someone in the family does not play baseball. We will see an example below under (what else) the Kruskal Math Family.

Who are the best Math families of all time? Here are some, not in order. I am sure there are more. Corrections and additions welcome! (I may make a website out of it.) I only count a family if it has at least three members and all of the people are related by blood (sorry Blums). Aside from that, I am fairly informal. This list is not meant to be the final word.

1. The Bernoulli Bunch Link. There were eight of them. Jakob-Bernoulli numbers, Nickolaus-Prob theory and Geometry (NOT Bernoulli Dist), Johann- Brachistochrone problem and possibly L'Hopital's rule, Daniel-Bernoulli's principal (also physics and probability), Wikipedia does not have info on the other four, but says they were math folks.
2. The Kruskal Kin: William (Kruskal-Wallace test in statistics), Martin (Solitons), and Joseph (Min Spanning tree, Kruskal Tree Theorem (set of all trees under embedding is a well quasi order), Kruskal-Katona Theorem). They are all brothers. Martin's son is Clyde (Parallel Computation, Coloring the Plane). Clyde's son is Justin (Ramsey Theory, though he's still in High School, so perhaps shouldn't count). William's son is Vincent (Computer Science-IBM research). Rosaly and Molly Kruskal are sisters of Martin/William/Joseph. They do not do math, but Molly has two sons who do math: William Kahn (statistician), and Ted Kahn (Statistical Software); and Rosalie's son is Jeremy Evnine (OR, Math Finance). (Using Clyde's theory these people would count some.) The following does not count as he is not a blood relative: Joe Kruskal's son-in-law is Neal Madras (Math prof at York Univ in Canada).
3. A Nest of Noethers: Father: Max Noether one of the finest mathematicians of the nineteenth century according to Auguste Dick who wrote a book on Emmy Noether. Max's son was Fritz Noether. Fritz Noether. Max's daughter was Emmy Noether the most important woman in the history of mathematics according to Einstein and others. (That was meant as a compliment but sounds so odd nowadays.) A great mathematician independent of her gender. The only father-son-daughter combination that I know of.
4. The Markov Chain: Andrey Markov (Markov Chains), his brother Vladmir Markov (Markov's inequality co-authored with his brother), and Andrey Markov Jr. (logic) son of Andrey Markov.
5. The Browder Brothers: Felix (PDE's), William (Topology and Geometry), and Andrew Browder (Analysis).
6. A Litter of Lenstras: Hendrik (Computational Number Theory), Arjen (Crypto), and Jan Karel.

Interesting misses:

1. A Research of Rabin's: Michael and Tal. A Father-Daughter both in Crypto. Probably the only such.
2. A Manifold of Millars: Terry and Jessica. A Father-Daughter both in Recursive Model Theory. Definitely the only such.
3. A Troop of Tardos': Eva and Gabor. The only other Brother-Sister combo I know of is the Noethers.
4. The Courant Clan: Richard Courant (Math), Hans Courant (son of Richard, Physics), Ernst Courant (son of Richard, Physics) Ted Courant (son of Hans, Math), Jurgen Moser (son-in-law of Richard, Math) Lucy Moser-Jauslin (Jurgen Moser's daughter, Math), Jerry Berkowitz (son-in-law of Richard, Math), Peter Lax (son-in-law of Richard, Math), Carl Runge (Father-in-law of Richard, Physics and Numerical Analysis). Note that Jurgen and Lucy Moser are a father-daughter combination.
5. A Band of Blums: Manuel and Lenore (married) and their son Avrim. All do TCS at CMU. Lenore-Avrim is the only mother-son combo I know.
6. A Geek of Gauss' or A Nerd of Newtons or An Egghead of Eulers or An Ark of Archimedes' are competitive with any of these families. But one person does not a family make.

Cleverness Squared

Many articles of interest in the New York Times.

Chris Maase pointed me to the article Scientists Disappointed by Direction of Financing.

Scientists, who were thrilled when President Obama vowed on his first day to "restore science to its proper place," have veered from excitement to dread as the stimulus bill makes its way through Congress.

I don't like the direction either, research funding down quite a bit from the original numbers in the stimulus plan. But I still expect science to get a nice boost from the stimulus. Did any of us guess back in December that the stimulus bill would have any science funding at all?

Steve Quake, a Stanford Bio-engineering professor, takes over as guest columnist on The Wild Side blog on the Times site. Quake's first column talks about the pressures of science funding.

I worry about the "opportunity cost" not only of the ideas not pursued and discoveries not made, but also of the time spent trying to convince very conservative review panels to fund one's research – each minute spent writing or administering grants is a minute that wasn't spent thinking deep thoughts about the frontiers of knowledge.

Could we stimulate more discovery and creativity if more scientists had the security of their own salary and a long-term commitment to a minimal level of research support? Would this encourage risk-taking and lead to an overall improvement in the quality of science?

I certainly have had my frustrations with the grant process and a few summers without salary in the past. Nevertheless the competition works well for us and we actually get more risk-taking to stand out from the pack.

Finally a new math puzzle, KenKen (Cleverness Squared), in the Times. So is the generalized n×n game NP-complete?

How Big is a Trillion?

Jason Hartline comments on a report by CNN about the size of the government bailout.

"To put a trillion dollars in context, if you spend a million dollars every day since Jesus was born, you still wouldn't have spent a trillion," McConnell said. CNN checked McConnell's numbers with noted Temple University math professor and author John Allen Paulos. "A million dollars a day for 2,000 years is only three-quarters of a trillion dollars. It's a big number no matter how you slice it," Paulos said.

Conclusion: At least one CNN reporter either doesn't know how long ago Jesus was born or cannot do basic arithmetic, so they found a mathematician who knows something about Jesus (John Allen Paulos is author of the book Irreligion: A Mathematician Explains Why the Arguments for God Just Don't Add Up) to ask for verification. Furthermore, the CNN editors found this to be reasonable investigative reporting. What!?!

Are results about actual constants interesting?

Josh Burdick had my course on concrete complexity a long time ago. He still dabbles in the area and recently sent me two manuscripts here and here

He seems to have proven the following:

PROBLEM: Given a 6 vertex graph (via (6 choose 2) Boolean inputs) you want to determine if it has a triangle. If you want to build a circuit for this problem just using NAND gates, how many are required.

PARTIAL ANSWER: The problem requires at least 21 NAND gates. ((6 choose 3), plus one output gate; what you'd probably expect, in other words.)

He has asked me two questions that I toss out to the audience

1. Is the result correct? (probably) Does it contradict anything known (I doubt that)? Does the proof seem correct? (I think so.)
2. Is the result interesting? To me this is the more interesting question (or meta-question). Are results about actual concrete numbers interesting? My first answer is only if (1) they lead to more more general results, or (2) use interesting techniques. So the answer may be, using (1), I DON"T KNOW, and (2) may be subjective.

The Ugly Proof

Alice: Does Carol's proof solve your big open problem?
Bob: Yes, but it's an ugly proof so it doesn't count.

A beautiful proof—a proof from "The Book"—is a piece of art. You take a look at it and just say "Wow!"

But what about the ugly proof. A boring case analysis that doesn't generalize and gives little to no insight as to why the theorem is true. A colleague, who for some reason wants to remain anonymous on this issue, has strong opinions about ugly proofs.

I guess the question is if there is a nicer proof or not. If there turns out to be, well and good. If not, probably it wasn't a very nice question. Nice questions have pretty answers.

I'm all for banning ugly proofs, except that there's likely to be a lack of agreement on what constitutes ugliness. The one positive aspect of an ugly proof is that it might lead to a nicer one. If not, it's worse than no proof at all.

I'm all for pretty proofs but if you have an open problem you care about, a need to get from point A to point B, while it is nicer to fly first class, getting to point B by driving a bumpy road still gets you to point B.

An ugly proof has the same logically correctness as a pretty one. Does the truth lack interest just because we had to take a painful path to get there?

New Blog on our blogroll: Be prepared to be blown away by BLOWN TO BITS

There is a new BLOG on our blogroll. It is Blown to Bits and it is associated to the book Blown to Bits: Your Life, Liberty, and Happiness after the digital Explostion by Hal Abelson, Ken Ledeem, and Harry Lewis.

1. The book is about how life has changed with the digital revolution. For more see my review either in an upcoming SIGACT NEWS or right here. Or better yet, buy the book.
2. The Blog will update the book. Note that there are events that happen in (say) 2009 that the book, published in 2008, would have wanted to cover, but couldn't. When we get time travel we can revisit this issue, and perhaps Abelso, Ledeem, Lewis will write a book on how that technology affects us. They won't need a blog to update the book.
3. The book Freakonomics has a blog associated to it. At first I didn't like the blog since I wanted it to be like the book. The book would take an observation or speculation and get real data on it and draw a conclusion. The blog would raise a question (Example: Why have paperboys on bicycles been replaced by papermen and paperwomen with cars?) and speculate (Example: it is more economically efficient) but not have any real information. This disapointed me since the books strength was to carefuly analyze. But now I like that blog since even raising issues is interesting (Example: I had not noticed that paperboys were being replaced by papermen and papewomen, but now I do.)
4. Similarly, the blog on BLOWN TO BITS cannot be as intellectually satisfying as the book. But it will be a good update on the book. And so far I have been very happy with it.
5. Disclosure: Harry Lewis was Bill Gasarch's advisor.

Stimulating Science

The stimulus package being shopped to congress by the Obama administration includes a considerable amount of science funding. The House passed a version that calls for an extra $2 billion dollars into core research at the NSF. The Senate is considering a bill that only gives an extra $1.2 billion for NSF core research. More details from AIP.

No doubt we need the additional funding. Scientific research has driven this nation's economy for many decades and we've let scientific research funding erode. The America Competes Act called for such funding but the full money has never been allocated. These funds, particulary the $2 billion, will put science funding back on track.

But does such increased science funding fulfill the main mission of the stimulus package, to get us out of the current recession and get people jobs now? Less clear.

Nevertheless the CRA is calling on us to contact our representatives in congress to push for the full science funding in the House stimulus bill. If we don't get science funding now, it will be very difficult to add it in the traditional budget process as the US faces a huge budget deficit.

While I was Gone

Just got back from vacationing in Obama's other home state and found a new govenor in Illinois when I got back. About time.

TTI-Chicago has moved into their new digs. Nice and spacious covering two floors soon to be connected by a bridge/stairway. And I get my own office for when I go down there.

Rocco Servedio is looking for a postdoc in learning/complexity at Columbia (email him if interested). Adam Klivans and David Zuckerman are looking for postdocs (plural) at UT-Austin. I've never seen a year with so many postdoc opportunities for complexity (and so few tenure-track jobs).

Paul Goldberg is looking for permanent faculty members (plural again) for a new Economics and Computation group in Liverpool. Economics is becoming the new quantum.

The Computational Complexity submission deadline is February 13, Electronic Commerce is February 9, ICALP is February 10th and many other conferences have deadlines very soon all vying for our just rejected STOC submissions. This list of papers that can't be submitted to another conference should, hopefully, appear here any moment now.

And you thought the STOC/FOCS deadline were pressure!

The James Bond Movie Goldeneye had the following scene which is typical of movies and some TV shows.

Scenario: A (good) female Russian computer programmer has made it really hard for the bad guys to do what they want to do. Boris is already working for the bad guys as a programmer.

BEGIN SCENE

HEAD BAD GUY: How long? (will it take to undo what she did)

BORIS: Two minutes... one minute.

HEAD BAD GUY: Guard! (he is calling over a guard who comes).

BORIS: I'm fixing it! (nervous)

HEAD BAD GUY: (to Guard) If he moves, kill him.

END SCENE

Boris was already on the bad guys side. Applying that kind of pressure seems counterproductive. Yet this is typical of bad guys in movies- they think that a threat of violence against a scientist already on their side will make them work faster- whether its programming or developing a nuclear bomb or whatever.

If the bad guy is trying to convince someone not on his side to work with him, then violence might make more sense. But even then, pressure may be counter productive. Better to offer the scientist a grant.