If you get a new result of interest with little effort...

Over the weekend I made an observation that gives a new (is it new?) lower bound on W(k,c). I will describe what all of this means, but my real interest are in the meta question if you have an easy proof of an interesting result, what to make of that?

Van der Waerden's theorem: For all k, for all c, there exists W=W(k,c) such that for all c-colorings of {1,...,W} there exists a,d such that a, a+d, ..., a+(k-1)d are the same color.

Chanda-Lipton-Furst showed (Lemma 4.4)

If there exists A, a k-free set (a set with no arithmetic sequence of length k) that is a subset of [n], then there is a c-coloring of [n] with no monochromatic arithmetic sequence, where c=O((nlog n)/|A|).

Laba and Lacey showed

There is a constant a such that, for all k that is a power of 2, for all n, there is a k-free set of size n× exp(-a(log n)^{1/(log k)}. (There result is sharper than this but this will suffice for us. They acknowledge that the result was already known in 1960 by Rankin.)

If you combine these two you obtain

W(k,c) &ge exp((log c)^{&Omega(log k)})

I have looked at the literature and used google and this appears to be new. I seemed to have proven something new and interesting with very little effort. I pose questions that anyone should pose in this situation and answer them for my case.

1. Is the result new? I think so- I've been looking at VDW papers for about 5 years now and have not run across it. Even so, would not be surprised (or even disappointed) if someone points to some paper I missed.
2. Is the result interesting? YES Upper bounds on VDW have gotten alot of attention. Lower bounds less so, but some. And they are a nice check on upper bounds.
3. Is the proof correct? In this case its just to easy to have gotten it wrong. (Famous last words...)
4. Are the results you used not commonly known to the same people? While the Chandra et. al paper is not well known to combinatorics people, its the same principle as the Symmetric Hypergraph Lemma, which is known. However, the k-free set result is not that well known.
5. Did the other people who knew all this stuff not care? Quite possible that the k-free set folks didn't care about this, or didn't think it was worth writing down.
6. Are you connecting two areas that have not been connected before? NO- k-free sets were studied because of VDW theorem.
7. What to do with the result? It deserves to be out there (for one thing, if I publicize it I may find out if its already known). I will probably write it up for a short note in some combinatorics journal (will check which ones take notes), and may put it on arXiv. Or might not bother hassling with referees (For more on that train of thought, see Zeilberg's opinion 77

If 50 is the new 40 then is 100 the new 80?

If you google 50 is the new 40 you get over 11,000 hits (fifty is the new forty gets only 961 hits). What does the phrase mean? It means that what a while back people did in their 40's they are now doing in their 50's. (Dating, Marrying, Having (perhaps more) kids, Changing Jobs, taking adult education classes, etc.) I tend to agree with this--- I often think that people in their 50's look like they are in their 40's. (The next generation won't have this problem as they will have adjusted to the shift--- unless there is another shift.)

So, if 50 is the new 40 then is 60 the new 50 ? Here is what Google says:

1. 60 is the new 50 got 3430 hits.
2. 70 is the new 60 got 788 hits.
3. 80 is the new 70 got 860 hits.
4. 90 is the new 80 got 193 hits.
5. 100 is the new 90 got 8 hits.
6. 110 is the new 100 got 2 hits.
7. 120 is the new 110 got 0 hits. You're 120! You don't look a day over 110!

(Note- these may go up because of this post.)

My intuition says that 120 is not the new 110. In fact, I think that 100 is still 100. So we are looking for a function f such that

1. f(50)=40
2. for all x ≥ 100, f(x)=x

Linear? log? piecewise linear? Is there a way to really find such an f? Only if you want to replace the intuitive statment 50 is the new 40 with a more rigourous one. Here is one example. Not sure what it would yield, or if you still really have 50 is the new 40 and 100 is the new 100. Let

1. g₁(x) = the life expectancy of someone who was x years old in 1950
2. g₂(x) = the life expectancy of someone who was x years old in 2008

(you may pick other functions that measure something about life then and now.)



With some rigorous definition you could really answer this question. But it may be more fun to put your math hat aside and just see what your intuition tells you. Mine says

1. 50 is the new 40.
2. 60 is the new 52.
3. 70 is the new 64. (will you still need me, will you still feed me, when I'm 70?)
4. 80 is the new 76.
5. 90 is the new 88.
6. 100 is the new 100. Or the old 100.

Announcement from source at NSF

(Guest posted by request from unnamed source at NSF.)

The Women in Science Award of the Maria Mitchell Association will recognize an individual who has worked to increase the participation and advancement of girls and/or women in science and mathematics.

To be considered for the Maria Mitchell Women in Science Award an individual must:

1. Demonstrate consistent leadership and support for the advancement of girls and women in the fields of natural and physical sciences, mathematics, engineering, computer science or technology.
2. Be someone who served as a mentor, role model or key player in a program designed specifically to encourage and advance girls and women in the fields of science, mathematics and technology.
3. Be a United States citizen

For more information on the award, please visit our website at here . Nomination forms must be = postmarked by March 15, 2008.

The Lance-Food Diet

As my long time readers know, I enjoy a good Francesinha as much as the next guy, but around the time of FCRC last June I realized I was simply getting too fat and had to do something about it. I would never last eating only so-called "healthy" food so I tried a different approach still eating the foods I love and I dropped forty pounds reaching my goal weight in November.

I should write a little pamphlet and sell it for $39.99 but for you readers I reveal my secrets for free.

• I went cold turkey on sweets. No brownies, no cakes, not even any non-fat frozen yogurt. Seminars and conferences offer us too many opportunities to partake of empty calories so best to have a hard and fast rule.
• Smaller portion sizes: One slice of pizza instead of two. A single hamburger instead of a double. Also fewer side dishes like fries.
• I cut out between meal snacks even if they don't seem too bad like pretzels. Do not eat when you aren't hungry.
• Avoid at all costs those evil green things commonly known as "vegetables." You'll never survive if you force yourself to eat stuff you don't like.
• I have been running three times a week, but this is no more than I did before the diet began.

Once I reached goal weight, I had another challenge—How to avoid losing too much weight without bouncing back up. I use the scale like a thermostat, eat less when I weigh more, and eat more when I weigh less, including the occasional ice cream.

Follow these simple rules and you too can lose weight the Lance way.

More on Graph Minors

Guest post by Vahan Mkrtchyan

(Sequel to Graph Minor Theorem Post)

When I was a student my supervisor used to explain me that one of the reasons why the P vs NP problem was not solved and why it could not be solved in near future, was the lack of techniques for proving the pure existence of polynomial algorithms for certain algorithmic problems.

In order to explain what he meant, consider a typical problem for an elementary course of calculus. Suppose we are given a function something like

f(x)=sin(exp(x²)-cos(x³-4x+7)-x⁴+6)

and we want to prove that this functions attains a maximum in some point from the segment [0,1]. How can we do this?

1. Possibility 1: just construct the maximum point
2. Possibility 2: reduce the problem to the finding of maximum of another function for which we already know its maximums.
3. Possibilty 3: Prove that f(x) is continious and apply Weiestrass theorem.

We know that neither Weierstrass theorem nor its proof imply anything about how one can construct this maximum. It just states that this maximum exists! Now suppose that we have a property P and we would like to show that testing P can be done in a polynomial time. How can we do that?

1. Possibility 1: just design a polynomial algorithm for testing P
2. Possibility 2: polynomially reduce the problem to testing another property P' for which we already have a polynomial algorithm

These two possibilities cover almost all the ways that reasearchers working on designing algorithms use while trying to prove the existence of efficient algorithms.

Fortunately, they cover almost all cases, since the Graph Minor Theorem implies that we have a

Possibilty 3: Prove that the property P is minor-closed, since Graph Minor Theory developed by Neil Robertson and Paul Seymour implies that all minor-closed properties can be tested in polynomial (even in cubic) time! Let us note a graph-theoretic property P is said to be minor-closed if whenever a graph G satisfies P then so does evey minor of G. This follows from

1. Graph Minor Theorem: If S is any family of finite graphs, none of which is a minor of another then S is finite!
2. The existence of a polynomial (cubic) algorithm for H-minor testing: Given a graph G. Is it true that H is a minor of G?

Incidentally the following problem is NP-complete: Minor testing Given two graphs G and H. Is it true that H is a minor of G? One might wonder whether there are properties for which we can prove the pure existence of a polynomial testing algorithm? As Reinhard Diestel states in his book Graph Theory, an example of such property is the knotlessness, that is deciding whether a graph can be embadded in 3-dimensional space such that none of its cycles form a trivial knot (see the book for details). Though we do know that the algorithm exists, at this moment we do not have an explicit algorithm (we cannot write a program), even if we have got enough enthusiasm to read Graph Minors I, Graph Minors II, Graph Minors III,..... - a series of papers devoted to the mentioned results of Robertson and Seymour.

One might wonder what can be said about graph minor theorem for infinite case. Robin Thomas in A counter-example to Wagner's conjecture for infinite graphs (Math. Proc. Comb. Phil. Soc. 1988, 103, pp. 55-57) constructed an infinite sequence of infinite graphs none of which is a minor of the other. Unfortunately, Thomas's proof contains two "bugs":

1. The proof heavily lies on the validity of the prominent Axiom of Choice from Set Theory. It would be extremely useful to understand whether the existence of such a sequence really depends on this axiom? To put it in more understanble form for the experts of Mathematical Logic, I would like to ask for the refutation of Graph Minor theorem in ZF-(minus) - Zermelo-Fraenkel set theory that does not include the axiom of choice? This question is interesting not only on its own, but also for the Countable Graph Minor Conjecture.
2. Thomas's proof implies nothing about the countable Graph Minor Conjecture, a conjecture stating that there are no infinite sequences of countable graphs none of which is a minor of the other?

Recent Developments: Bruce Reed and Ken-ichi Kawarabayashi have recently reduced the complexity of H-minor testing to O(n logn). "...To cast a glance at the next advaces of our science and the secrets of its development..." (the sentence is taken from David Hilbert's epochal talk before the International Congress of Mathematicians at Paris in 1900), especially for the generalization of the Graph Minor Theorem to Matroids (=Graph Minor Project) see Jim Geelen's lecture-notes delivered by him in the recent ADONET-CIRM doctoral school on Graphs and Algorithms.

The End of TV as I Knew It

It was one of the great mysteries of my childhood. You changed TV stations by turning a dial, a dial that started at "2". What happened to channel 1? So off I went to the library and found out the ugly truth: Channel 1 contains the entire FM spectrum. Each TV station took a very wide spectrum to send off their analog signals.

But as of February 2009 the rest of the analog channels will disappear as well. Today the FCC starts the auction for that spectrum. FCC spectrum auctions are the poster child for combinatorial auctions where bidders bet on subsets of goods and have lots of nifty complexity issues. But I don't want to talk about math today, just want to mourn the analog space that carried the classic TV shows I watched as a kid. The moon landing was broadcast live over those airwaves about to be sold off forever.

Much ado is made about Google entering the bidding. But the spectrum will likely go to major telecoms like AT&T and Verizon. They will use the spectrum mainly for high-speed wireless data. And what will we use that high-speed data for? Watching TV on our cell phones. The circle will be complete.

Optimizing your vote

First off, I am delighted that Lance is back! I don't think this picture of Lance looks like him. I'm looking forward to meeting Jason and Nicole (at CCC 2008?) to see if they look like themselves. Second off- A post on politics.

This is not a post expressing any particular political viewpoint. Here is the question: Is it always best to vote for who you actually like best in the primary elections?

Consider the following scenario. I use real names, but the ratings are made up just for this problem and do not reflect mine or Lance's opinions.

Say you rank the current candidates in the following order with the following scores on a 10 point scale:

1. Obama: 8.8 (acceptable) Democrat
2. McCain: 7.8 (acceptable) Republican
3. Paul: 7.5 (acceptable) Republican
4. Clinton: 7.0 (acceptable) Democrat
5. Edwards: 6.8 (acceptable) Democrat
6. Thompson: 6.0 (not acceptable) Republican
7. Huckabee: 5.8 (not acceptable) Republican
8. Romney: 5.0 (not acceptable) Republican

Also say that you are in a state where you can vote in either the Democratic or Republican primary (but not both). We could also have numbers for how likely they are to win the nomination (e.g., why vote for Ron Paul when he doesn't have a chance). We could also have numbers for each pair of Republican and Democrate as to who would win the general election (e.g., you may vote for Huckabee because you think that Obama, Clinton, and Edwards all have a good change to beat him in the general election, so you want him to be the nominee. Of course, this is a dangerous strategy since he might win and you didn't think he was acceptable. Also, you DID like McCain so...)

Given all of this data, who should you vote for? Can this problem be made rigorous and solved? Of course, the really hard part in the real world might be getting those numbers. And you may have other reasons to vote, as shown by this ad:

Politics and The Blog

One cannot escape the tight races for the democratic and republican nominees for president. While I would never endorse any specific candidate on this blog, one cannot ignore the race and the various mathematical aspects of the elections. I helped, in a very small way, with the design of the Yahoo Political Dashboard, that really boils the race down to just a bunch of numbers, perhaps a bit too much.

The Electoral College comes often comes into criticism but at least it is essentially just a weighted majority of pluralities. States, on the other hand, allocate their delegates in a variety of different and confusing ways. Right now news agencies seem to just count state wins but after February 5 expect some interesting analysis of delegate counts.

A little game theory: Why does John Edwards stays in the race when he has a virtually zero chance of getting a majority of the delegates? Because there is a non-zero probability that neither Obama or Clinton will have a majority either, and then Edwards wields incredible power with his small number of delegates. I don't know what Edwards would do with this power, but he won't give it up by dropping out of the race.

Notice that when we have a surprise victory in a primary, like Clinton in New Hampshire, much of the talk revolves on why the pundits, polls and prediction markets all "failed." Meanwhile in sports when we see a surprise victory, like the New York Giants over Dallas and then again in Green Bay, the focus is on what the Giants did right and the Cowboys and Packers did wrong. Sports fans understand probabilities much better than political junkies—upsets happen occasionally, just as they should.

Bobby Fischer (Guest Post by Ken Regan)

When I watched the Fischer-Spassky match on TV back in 1972, there was a young chess prodigy, just a few years older than me, helping with the commentary of the games. That kid grew up to be Complexity theorist Kenneth Regan and I asked Ken to give some personal comments on Bobby Fischer, who passed away yesterday.

Bobby Fischer lived 64 years, one for each square on the chessboard. Unfortunately most of those squares were empty of playing the game he loved at the highest levels, but the brilliance and spirit of his games and ideas will ensure his board is remembered as more than half full.

What impressed me from Fischer's games was that clear logic and dynamism can both be harnessed. He produced scintillating attacks of the kind we associate with Tal and Kasparov, and positional masterpieces worthy of Capablanca and Karpov—including Game 6 of his 1972 match with Spassky. Kasparov is known for researching new ways of sacrificing pawns in the opening to increase the energy of one's position, while Fischer always maximized the potential of the position to hand. Almost uniquely with him there were no early draws while there was fight left. Other champions are known for how many years they went without losing a game, whereas Fischer won 19 games in a row, in the world championship stages. This ethic rubbed off on me even when I found myself paired against a fellow teen master I'd just shared a long bus ride with from Princeton to NYC. He sensibly proposed an immediate draw so we could rest, but I was there to play—and I lost!

I was attracted to the game just before the "Fischer Boom" years, and had nearly reached master level at age 12 when the Fischer-Spassky match began. I was on the nationwide PBS live broadcast of two of those games as an expert commentator assisting Shelby Lyman's TV coverage. My own rise was aided much more directly by the tournaments organized on a nationwide scale by William Goichberg, who is now President of the US Chess Federation. I never played Fischer—I met him only once in an elevator when he visited one of those tournaments. I was the age to feel the letdown most deeply when he did not play after 1972 and did not defend his title against Karpov in 1975, though what we've learned about his personal travails since then removes blame and much regret over this. Still, a piece of Brooklyn died with me yesterday.

Fischer will also be known for innovations of "Why didn't anyone else think of that?" caliber. The Fischer Chess Clock is now standard equipment. It regulates a player's time allotment in the manner of Social Security so that each move always has some thinking time. The Fischer Castling Rule enables the game to be started from different initial configurations while retaining its character. Fischer Random chess has both players start with the same random choice from 960 placements of pieces on the back row, and is gaining traction as more people agree with Bobby that computers and vast encyclopedias of opening analysis are causing the standard opening configuration to be "played out." I favor "non-random" placements with Black allowed to differ from White in my proposal Baseline chess with Fischer rules. Fischer also feared that computers would ruin the mystery of chess, but I can personally vouch that the game's incredible complexity remains. In response to the challenge compliment from Grandmaster Susan Polgar's premier chess blog, I undertook to tell whether (now ex-) World Champion Vladimir Kramnik missed a win at Move 50 on the slippery slope to losing his title last September. After four months and 300+ pages of analysis, aided by Deep Fritz 10 and two other chess programs running on faster hardware than DF10 used to beat Kramnik a year ago, having sifted over 20 trillion search nodes and tried out almost 100,000 moves, I'm about to throw up my hands and say I have no opinion more definite than "flip-a-coin" on whether White can win!

Lance 2.0

The weblog has called me back. Bill and I will now jointly be posting on this blog.

Many changes in my life since last March, most importantly starting a new job at Northwestern. Jason Hartline, building on an idea of Nicole Immorlica, had a poster made announcing our new group.

Can you guess the movie reference? Hint: I am standing in for Richard Gere.

Don't let the poster scare you—Computational Complexity will always remain my one true academic love.

If you submitted a CDI proposal READ THIS

Guest REQUEST by Richard Beigel- NSF Guy. (I always forget formal titles.)

The CDI program received around 1300 proposals. You can imagine the difficulty and importance of assigning the proposals to appropriate panels. If you submitted a CDI proposal relevant to theory of computing please send an email Richard Beigel immediately and in any case by close of business Friday January 18. You can find his email address here:
here

If possible, include your Proposal ID Number when writing.

Math books you can actually read

How many math books can you read cover-to-cover? How many have you? The problem is that while you can certainly read any discrete math (for ugrads) textbooks cover-to-cover you don't want to- you know most of it.

Computer Science Theory is better than math for this since the field is younger and the books often do not need as much background.

So, which books are just right- hard enough to have things in them of interest, but not so hard that you can't read them. Demanding you be able to read it `cover-to-cover' is rather demanding and also ambigous- do you need to understand everything? I'll define this to just be `read/understood over 90% of the book'

With that in mind, here are the books I've done that for. Its a short list.

1. Recursively Enumerable Sets and Degrees by Soare. I had a course in 1980 (by Michael Stob- a PhD student of Soare) that covered about 1/2 of it (in preprint form). I understood about 3/4 of that course. But over the next 20 years I (slowly) read and understood the rest. By 2000 I had it all. I try to retain it by presenting a priority argument argument to someone once in a while. Its getting harder to find someone who wants to see these things who doesn't already know them. I did drag Steven Fenner into a room at CCC06 and forced him to see the proof that there is a minimal pair of r.e. degrees using a tree argument,
2. Ramsey Theory by Graham, Rothchild, Spencer. I had about 1/3 of this in a course (by Spencer) in 1978. Over the next 30 years I've read more of it. Now I'm about done.
3. Linear Orderings by Rosenstein. Great book, out of print now. Does lots of model theory (E-F games) and recursion theory in a more concrete setting.
4. I've read several books by Brams and Taylor about fair division. All are readable. The nice things here is that the math is easy but probably new to most of us. Hardest theorem: there is an envy free discrete protocol to divide a cake between 4 people (or more).
5. Communication Complexity by Kushilevitz and Nisan. Reviewed it and used it in a course twice. By the second time I had it all read.
6. Proofs that really count by Benjamin and Quinn. This is about proofs of combinatorial identities done by showing that two expressions solve the same problem. Great topic, Great book.

So how about you- have you found many book that hit that sweet spot between too easy and too hard. And that are well written.

Invited Post on Invited Speakers Website

Iftah Gamzu requested that I post on the following topic. When I began to do it, I realized that his email to me, edited slightly, says it all and says it all well. So here is a guest post by Iftah Gamzu:

My name is Iftah Gamzu, and I'm a PhD student in Tel Aviv University. Some time ago, several people brought to my attention the need for a web page that will list past invited speakers in theory conferences. They mentioned that such web page would help program committees, and especially program chairs in the decision of who to invite to present plenary talks. Consequently, I devised such web page

here

Unfortunately, there are still missing pieces of information that I couldn't track down on the web. SO, if you know some of the missing info, please email me at

iftgam@post.tau.ac.il

Today is Knuth's 70th birthday!!

Today, January 10, is Donald Knuth's 70th birthday. I have some thoughts on Knuth, but I am sure that my readers have more. So, I'm asking you to leave comments on Donald Knuth. Let's break the record for number-of-comments on an entry. Knuth deserves it! (What is the record? If I were as meticulous as Knuth I would know.)

1. My first exposure to Knuth's work was in 1980 when I was doing a survey on Factoring Polynomials over Finite Fields. I couldn't find the relevant papers in the library (I can hear people under 25 saying weren't they on line? or what's a library?), so I was told to look in Knuth Volume 2. And indeed, there was a wonderful exposition of what I needed to know, and the history behind it. Quite scholarly and, unfortunately, quite rare among other researchers.
2. Browsing through Knuth's volume I got the impression that his attitude is I want to solve problem X and I'll use whatever math I need to solve it, even if I have to develop it myself. Never shy away from a problem because you don't know the math needed, or even because the math you need hasn't been developed yet.
3. TeX: Reading the TeX manual you actually learn things of interest outside of TeX. Not only did I learn how to hyphenate in TeX, I also learned that in German when you hyphenate some words, you actually change their spelling. And, of course, TeX can handle this.
4. TeX and LaTeX: Revolutionized how we write papers. Facilitated the notion of keeping papers on line for easy access.
5. First Contact!: I got a postcard from Knuth pointing out an error in a paper I wrote. WOW! a postcard from Knuth.
6. Second Contact!: Knuth asks me to get a review of Volume 4 in my book review column. I was surprised that he emailed me (he does not use email) and amazed that Volume 4 was coming out. The way he asked me was interesting: see this post
7. I always thought Volume 4 was a myth, like the missing part of the Dead Sea scrolls. How long has the world been waiting for Volume 4? Knuth needed a term for what we know as `NP-completeness' for use in Volume 4. He held a contest, and NP-completeness won. (He ended up not using it in Volume 4.)
8. Volume 4: Yes, it really is out, sort of. It's coming out as a series (or a sequence) of fascicles (small books) of (I am not making this up) exactly 128 pages. It's on generation of combinatorial objects. The second fascicle, on enumerating all strings of length n, (e.g., Gray codes) is fascinating. Includes history and the needed mathematics. History goes back to the mid 1850's. Quite scholarly and, unfortunately, quite rare among other researchers.
9. What has Knuth's influence been on computer science? He was one of the first people to realize that an algorithm can be analysed in a mathematical and intelligent way without running it. This is one of the most important starting points for computer science theory. Perhaps even for computer science.

predictions for 2008 and beyond

Predictions for 2008 and beyond:

1. In October the Democratic pundits will predict that the Democrat will win the election, and the Republican pundits will predict that the Republican will win the election.
2. There will be a big breakthrough in theory. Very hard to predict what it will be- note that this years big breakthrough, faster algorithm for integer multiplication, would have been hard to predict.
3. P vs NP, P vs BPP, will not be solved.
4. Computer science enrollment will rise slightly.
5. There will be a paper claiming to resolve P=NP. Some students will email me asking if it is worth reading. I'll say no.
6. Medium Term- The Spam problem will get worse.
7. Long Term- Self-checkout will become more and more common in grocery stores and other stores.
8. Long term- the business model for academic publishing, both journals and monographs, will change. It has too.
9. Long term- women will stop taking their husbands names, because taking their names would be google-stupid
10. Long term- people will give their kids names based on how easy it is to find on google.

The Past and the Future in Song Form

The past and the future use the same tune:

The past: 2007, they disabled embedding so could not put it here directly. Clearly old-school business model



The future:



<\object>

Graph Minor Theorem and Non Const Algorithms

The last comment on the last post had some questions about the graph minor theorem and (implicitly) nonconstructive algorithms in general. Here is some background and answers.

1. If G is a graph then H is a minor of G if H can be obtained by removing vertices, removing edges, and constracting edges (that is, replacing edge (u,v) with just one vertex that has all the neighbors that u and v had).
2. The formal statement of the Graph Minor Theorem (GMT)is: the set of graphs with the minor ordering is a well quasi order. This means that you cannot have an infinite descending sequence of graphs or an infinite set of incomparable graphs, using this ordering.
3. The GMT has a hard nonconstructive proof. It was proven in a sequence of papers by Robertson and Seymour entitled `Graph Minors I' `Graph Minors II' etc. It was finally proved in Graph Minors XX. This website claims that it was proven in 1988 but was not published until 2004.
4. The proof is not only nonconstructive, but it is provably nonconstructive using Harvey Frideman's Reverse Mathematics framework.
5. The following two facts, one a corollary of the GMT, is what yields polytime algorithms:
   1. For a fixed graph H, there is an O(n³) algorithm for the problem: Given G, is H a minor of G.
   2. If X is a set of graphs closed under minor then there exists a FINITE set of graphs H₁,...,H_a such that G \in X iff NONE of H₁,...,H_a are minors of G. (This is the corollary to GMT.) EXAMPLE: a graph is planar iff it does not have K_3,3 or K₅ as a minor. In this case we know the obstruction set. The proof of GMT does not yield this information.
6. One easily obtains poly time algorithms (indeed O(n³)) for many problems. Here are two such.
   1. Fix k. Test if a graph has Vertex Cover of size &le k. (VC_k)
   2. Fix g. Test if a graph has genus &le g.
7. There are constructive linear time algorithms for the VC_k. Last time I checked it was down to O(n + (1.34)^k). For the Genus problem I don't know whats known. (Commentators- please comment.)
8. Fellows and Langston showed how to convert most algorithms (including those for VC and Genus) from poly nonconst to poly constructive. The degree does not go up much (either by 0 or 1), but the order constant gets even worse.
9. NOW for the commentators question: is the converse true: does an algorithm for (say) genus g that is in time O(n³) (the order constant may depend on g) imply GMT. I doubt this is true. It may be provably not true given that GMT has a provably nonconstructive proof.
10. Are there other nonconstructive algorithms? A cheap example are things like
    f(k) = 1 if SAT is in TIME(n^k), 0 otherwise
    which is in P (its just a step function or the always 0 function) but do not know how to compute it. Are there examples for problems we care about being in P through nonconstructive means that are NOT from GMT? I do not know. Commentators-please comment.
11. There are many problems in NP where if you fix one parameter they are in O(f(k)p(n)) and not O(n^f(k)). Such problems are called FIXED PARAMETER TRACTABLE. Downey and Fellows wrote a book on it a while back, though there are more books out now.
12. Are there more legit examples? Commentators- please comment.
13. I will have a later post on nonconstructive things in math.

2007 Complexity Year in Review

Guest Post by Lance Fortnow

We had quite an active year in complexity and Paper of the Year goes to Martin Fürer's Faster Integer Multiplication, making a breakthrough in this most basic of algorithmic questions.

This blog, now under new leadership, hit five years and 1000 posts in August. Most commented post: Vijay Vazirani's post suggesting that submissions to conferences come with an accompaning video followed closely by Claire Kenyon's post on cover letters.

Back in February I posted about large proposed increases in the NSF budget but with a caveat that it had to survive the congressional appropriation process. It didn't.

In 2007 we mourned theorists Steve Mahaney and Andrej Muchnik as well as others close to our heart: Martin Kruskal, Jim Gray, John Backus and Paul Cohen.

Bill and I would like to thank our guest posters Kamal Jain, Jonathan Katz, Claire Kenyon, Shiva Kintali, Phil Klein, Stuart Kurtz, Clyde Kruskal, Nicole Immorlica, Amir Michail, Mihai Patrascu, Ken Regan, Jim Royer, Alexander Shen and Vijay Vazirani. Most of all thanks to Bill for keeping this blog active and still going strong.

Here's wishing everyone a great 2008!

Presidential Math

On Jan 3 is the Iowa Caucus, the first contest (or something) in the US Presidential race. The question arises: Which presidents knew the most mathematics? The question has several answers depending on how you define "know" and "mathematics". Rather than answer it, I'll list a few who know some mathematics.

1. Jimmy Carter (President 1976-1980, lost re-election) was trained as a Nuclear Engineer, so he knew some math a long time before becoming president. (I do not know if he ever actually had a job as an Engineer.) I doubt he knew much when he was president.
2. Herbert Hoover (President 1928-1932, lost re-election) was a Mining Engineer and actually did it for a while and was a success. Even so, I doubt he know much when he was president.
3. James Garfield (President 1881-1881, he was assassinated) Had a classical education and came up with a new proof of the Pythagorean Theorem
4. Thomas Jefferson (President 1801-1809) had a classical education and is regarded by historians as being a brilliant man. He invented a Crypto system in 1795. Note that this is only 6 years before becoming president, so he surely knew some math when he was president.
5. Misc: Lyndon B. Johnson was a high school math teacher, Ulysses S. Grant wanted to me one but became president instead. George Washington was a surveyor which needs some math. Many of the early presidents had classical educations which would include Euclid. And lastly, Warren G. Harding got an early draft of Van Der Waerden's theorem, conjectured the polynomial VDW, but was only able to proof the quadratic case (not surprising—he is known as one of our dumber presidents).

I would guess that Jimmy Carter and Herbert Hoover knew more math (there was far more to know) then Jefferson, but Jefferson knew more as a percent of what there was to know, then Carter and Hoover. Garfield, while quite smart, probably does not rank in either category. I don't think any of the current major candidates were trained in Math. Hillary Clinton, Barack Obama, John Edwards, Rudy Guilliani, and Mitt Romney were all trained as lawyers. Rudy Guillian and Mitt Romney have been businessman as well. Huckabee was a minister, McCain was a soldier. I do not know what they majored in as undergrads.

Oral Homework

This fall in my graduate complexity courses 5/11 of the HW were group HWs. This means that

1. The students are in groups of 3 or 4. The groups are self-selected and permanent (with some minor changes if need be).
2. The groups do the HW together.
3. They are allowed to use the web, other students, me, other profs.
4. The HW is not handed in–they get an Oral Exam on it.
5. The HW is usually "read this paper and explain this proof to me."

In my graduate course in Complexity Theory which I just finished teaching 5 out of the 11 HWs were Oral HW. Here is what they were basically:

1. Savitch's theorem and Immerman-Szelepcsenyi Theorem.
2. Show that VC and HAM are NPC.
3. E(X+Y)=E(X)+E(Y), Markov, Chebyshev, Chernoff
4. Reg Exp with squaring NOT in P.
5. Matrix Group Problem in AM. (Babai's paper "Trading Group Theory for Randomness").

Was this a good idea?

1. The students learned ALOT by doing this. They learned the material in the paper, they learned how to read a paper, and they learned how to work together. (Will all of these lessons stick?)
2. Some proofs are better done on your own than having a professor tell you them (HAM cycle NPC comes to mind). This is a way to make them learn those theorems without me having to teach it.
3. Some theorems are needed for the course, but are not really part of the course (Chernoff Bounds come to mind). The Oral HW makes them learn that.
4. This was a graduate course in theory so the students were interested and not too far apart in ability. This would NOT work in an ugrad course if either of those were false.
5. This course only had 19 students in it, so was easy enough to administer.

So the upshot–It worked! I recommend it for small graduate classes.

The Twelve Days of Tenure

On the twelfth glance at her case, what did we all see:

12 people asking her questions in her office, 11 times taught Intro Programming, 10 journal articles, 9 pieces of software, 8 book chapters, 7 invited panels, 6 submitted articles, 5 mil-lion bucks!, 4 invited talks, 3 students, 2 post-docs, and a degree from MIT.

NOTE: The 12 days of Christmas is (easily) the most satirized song ever. I used to maintain a website of satires of it here but it was too hard to keep up? Why? Because anyone can write one. I wrote the one above in about 10 minutes during a faculty meeting to decide someone's Tenure case.

A Bad Deal

Bill Gasarch is on vacation and he had given me (Lance) a collection of posts for me to post in his absence. But then I got email from Tal Rabin who wants to get the word out about the Women in Theory workshop to be held in Princeton in June. Done. Now back to your regularly scheduled post from Bill.

---

I don't usually watch Deal/No Deal. I like some of the interesting math or dilemmas it brings up, but the show itself is monotonous. As Host Howie Mandel himself says "we don't ask you a bunch of trivia questions, we just ask you one question: DEAL or NO DEAL!" Here is a scenario I saw recently where I thought the contestant made the obviously wrong choice.

1. There are two numbers left on the board: $1000 and $200,000.
2. She is offered a $110,000 deal.
3. She has mentioned that $110,000 is about 5 times her salary (so this amount of money would make a huge difference in her life).
4. Usually in this show you have the audience yelling `NO DEAL! NO DEAL!' This time the audience, including her mother, her sister, and some friends, were yelling `TAKE THE DEAL! TAKE THE DEAL!'. While this is not a reason to take the deal, note that the decision to say NO DEAL is NOT a `caught up in the moment' sort of thing.

She DID NOT take the deal. We should judge if this was a good or bad decision NOT based on the final outcome (which I won't tell you). Here is why I think it was the wrong choice. Consider the following scenarios:

1. If she takes the deal, the worst case is that she gets $110,00 instead of $200,000.
2. If she rejects the deal, the worst case is that she gets $1000 instead of $110,000.

The first one is not-so-bad. The second is really really bad. Is there a rational argument for her decision? I could not come up with one, but maybe I'm just risk-averse.

More on VDW over the Reals

Some of the comments made on the posts on this post on a VDW over the Reals been very enlightening to me about some math questions. In THIS post I will reiterate them to clarify them for myself, and hopefully for you.

I had claimed that the proof that if you 2-color R you get a monochromatic 3-AP USED properties of R- notably that the midpoint of two elements of R is an element of R. Someone named ANONYMOUS (who would have impressed me if I knew who she was) left a comment pointed out that the proof works over N as well. THIS IS CORRECT:

If you 2-color {1,...,9} then there will be a mono 3-AP. Just look at {3,5,7}. Two of them are the same color.

1. If 3,5 are RED then either 1 is RED and we're done, 4 is RED and we're done, or 7 is RED and we're done, or 1,4,7 are all BLUE and we're done.
2. If 5,7 are RED then either 3 is RED and we're done, or 6 is RED and we're done, or 9 is RED and we're done, or 3,6,9 are all BLUE, and we're done.
3. If 3,7 are RED then either 1 is RED and we're done, or 5 is RED and we're done, or 9 is RED and we're done, or 1,5,9 are BLUE and we're done.

This is INTERESTING (at least to me) since VDW(3,2)=9 is TRUE and this is a nice proof that VDW(3,2)≤ 9. (Its easy to show VDW(3,2)≠ 8: take the coloring RRBBRRBB.) I had asked if VDWr may have an easier proof then VDW. Andy D (Andy Drucker who has his own Blog) pointed out that this is unlikely since there is an easy proof that VDWR--> VDW. Does this make VDWr more interesting or less interesting? Both!

1. More Interesting: If VDWr is proven true using analysis or logic, then we get a NEW proof of VDW!
2. Less Interesting: Since it is unlikely to get a new proof of VDW, it is unlikely that there is a proof of VDWr using analysis.

Bad News for American Science Funding/Good News for Australia Science Funding

Bad news for American Science Funding: click here

Good news for Australian Science Funding: click here

Complexity Theory Class Drinking Game

Complexity Theory Class Drinking Game

1. Whenever a complexity class is defined that has zero natural problems in it, take one drink.
2. Whenever a class is defined that has one natural problem in it, take two drinks.
3. Whenever you are asked to vote on whether or not a problem is natural, take three drinks.
4. Whenever a mistake is made that can be corrected during that class, take one drink.
5. Whenever a mistake is made that can be corrected during the next class, take two drinks.
6. Whenever a mistake is made that cannot be corrected because it's just wrong, take three drinks.
7. Whenever a probability is amplified, refill your cups since a class with zero or one natural problems in it is on its way.
8. Whenever the instructor says that a theorem has an application, take a drink.
9. Whenever the instructor says that a theorem has an application, and it actually does, take two drinks.
10. Whenever the instructor says that a theorem has an application outside of theory, take two drinks.
11. Whenever the instructor says that a theorem has an application outside of theory, and it really does, take four drinks.

An ill define question inspired by that HS question

RECALL the problem from my last post:

Each point in the plane is colored either red or green. Let ABC be a fixed triangle. Prove that there is a triangle DEF in the plane such that DEF is similar to ABC and the vertices of DEF all have the same color.

The answers to all of the problems on the exam are posted See here for the webpage for the competition. The problem above is problem 5.

One of the key observations needed to solve the problem is the following theorem:

If the reals are 2-colored then there exists 3 points that are the same color that are equally spaced.

Before you can say `VDW theorem!' or `Roth's Theorem!' or `Szemeredi's theorem for k=3 !' realize that this was an exam for High School Students who would not know such thing. And indeed there is an easier proof that a HS student could (and in fact some did) use:

Let a,b both be RED. If (a+b)/2 is RED then a,(a+b)/2,b works. If 2b-a is RED then a,b,2b-a works. If 2a-b is RED then 2a-b,a,b works. IF none of these hold then 2a-b,(a+b)/2,2b-a are all BLUE and that works.

By VDW the following, which we denote VDWR, is true by just restricting the coloring to N:

VDWR: For any k,c, for any c-coloring of R (yes R) there exists a monochromatic arithmetic progression of length k.

This raises the following ill-defined question:

Is there a proof of VDWR that is EASIER than using VDW's theorem. Or at least different- perhaps using properties of the reals (the case of c=2, k=3 used that the midpoint of two reals is always a real).

Funny Answers on a Math Olympiad (MD)

I was assigned to grade the following problem from the Maryland Math Olympiad from 2007 (for High School Students):

Each point in the plane is colored either red or green. Let ABC be a fixed triangle. Prove that there is a triangle DEF in the plane such that DEF is similar to ABC and the vertices of DEF all have the same color.

I think I was assigned to grade it since it looks like the kind of problem I would make up, even though I didn't. It was problem 5 (out of 5) and hence it was what we thought was the hardest problem. About 100 people tried it, and less than 5 got it right, and less than 10 got partial credit (and they didn't get much).

I got two funny answers:

All the vertices are red because I can make them whatever color I want. I can also write at a 30 degree angle to the bottom of this paper if thats what I feel like doing at the moment. Just like 2+2=5 if thats what my math teacher says. Math is pretty subjective anyway. (NOTE- this was written at a 30 degree angle.)

I like to think that we live in a world where points are not judged by their color, but by the content of their character. Color should be irrelevant in the the plane. To prove that there exists a group of points where only one color is acceptable is a reprehensible act of bigotry and discrimination.

Were they serious? Hard to say, but I would guess the first one might have been but the second one was not.

Crypto problem inspired by politness

The following happened- a common event, but it inspired a crypto question (probably already known and answered) but I would like your comments or pointer to what is known.

My mother-in-law Margie and her sister Posy had the following conversation:

POSY: Let me treat the lunch.

MARGIE: No, we should pay half.

POSY: No, I want to treat.

MARGIE: No, I insist.

This went on for quite a while. The question is NOT how to avoid infinite loops- my solution to that is easy- if someone offers to treat, I say YES and if someone offers to pay 1/2 I say YES, not because I'm cheap, but to avoid infinite loops.

Here is the question. It is not clear if Posy really wanted to treat lunch, or is just being polite. Its not clear if Margie really wants to pay half or is just being polite. SO, is their some protocol where the probability of both getting they DO NOT WANT is small (or both getting what they want is large), and the other one does not find out what they really want. Here is an attempt which does not work.

1. Margie has a coin. Margies coin is OFFER with prob p, and DO NOT OFFER with prob 1-p. If she really wants to make the offer to treat then p is large, else p is small. Could be p=3/4 or p=1/4 for examples.
2. Posy has a similar coin.
3. Margie flips, Posy Flips.
4. If Margie's coin says OFFER, than make the offer. If not the don't.
5. Same with Posy.

The bad scenarios- that they both get what they don't want, has prob 1/8. However, if they do this alot then Margie and Posy will both have a good idea of what the other really wants.

In solutions you may offer or point me to we can of course assume access to random coins, and that neither Posy nor Margie can factor or take discrete log.

Sending out Job Applications

Sending out job applications

(Guest Post by Claire Kenyon)

This is the time of year when job candidates are getting ready to send out their applications. I have done this many times over the years. Here are a few suggestions based on my experience.

Candidates want to find a job where they will be successful; department want to hire candidates who will be successful in their job: this is not inherently adversarial; it's just a question of finding the right match.

Cover letter:

1) Don't call a place "College" if it's a "University", and vice-versa. Get the names of committees and of people right. Obvious, yet, it took me a few years to learn this!

2)How to get the reader to look beyond the cover letter? Catch their attention. Give a specific reason why you are interested in that place; preferably personal (something that says something about you, and that few other candidates are likely to say.) "I am interested in the computer science department at University Lambda because of its unique research interest in Reducing the Number of Greek Symbols in Analysis of Stuff, and its joint project with the Humanities department on that subject. My publications have a lot of greek symbols in them (see [1,2,3,4,5] for example), and I would be very interested in applying the lambda methodology to my work."

3) How to get the reader to forward your application to the right person? Give specific names. For example:

Professor Big Shot, who I met during the 2007 Symposium on Theory of Unreasonable Protocols for Integer Data (see [3]), encouraged me to apply.

That context will help Big Shot place you in their memory when they get the application.

4) Be self-consistent. Do not tell UC Big

I just love the idea of public service in the rich environment of a large university

and simultaneously tell Happy University

I love the idea of mentoring a small group of select students in the focused environment of a small high-quality university.

The reasons are that this may become known (we do talk to one another) and would cost you your credibility; that you won't be able to follow through by arguing convincingly both ways; and that such blatant mis-representation of yourself makes it more difficult to find the right match.

5) Read the ad, and address obvious issues upfront.

You said you're looking to hire a researcher in human-computer interaction using ergonomic mouse pads, and my area, cryptanalysis of public-key cryptosystems using elliptic curves, may at first sight look somewhat remote; however there are surprising connections that I intend to reveal in my future research: elliptic curves

Google-stupid

The May 8 2007 issue of THE WALL STREET JOURNAL has the following on the front page:

You're a Nobody Unless Your Name Googles Well

The article told the story of a women who got married and took her husbands name, hence going from an uncommon, first-page--google-name, to a common 85th-page-google-name. This hurt her career. When considering what to name her children she used Google to make sure that her kids would have names that pop up on the first page of a Google search.

When considering naming your child how do the following rank in importance?

1. Honoring a family member.
2. Carrying on a tradition.
3. If you are religous, using a name from your faith (e.g., I know a Christian who uses only biblical names for his four kids- alternating Old Testament and New Testament).
4. First Page on a Google Search.

I predict that in the future item 4 will be the most important and the other ones will not even be understood. My great niece will one day tell me

Uncle Bill, did people really name their children after themselves? Thats just google-stupid.

Unrefereed DOES NOT EQUAL bogus

Based on some of the comments on the last two posts it seems that some of our community is of the mindset that having a conference where everything gets in is a bad thing. This is not necc true. Here are some conferences for contrast.

1. STOC, FOCS, SODA, CCC, LICS, MFCS, ICALP, COLT, CRYPTO, EUROCRYPT, STACS, SCG (I'm sure there are others). Strongly Refereed (acceptance rates all under 50 percent, some much lower), there is a proceedings, there may or may not be guest speakers. Registration 400-600 dollars. Authors not forced to pay for the honor of being authors. This notion would strike every particpant as unusual to say the least.
2. Annual AMS meeting. There are a large number of contributed papers (unrefereed) in specialized areas. No proceedings. There are guest speakers. Registration 400-500 dollars. Note that while the contributed papers are not refereed there is no claim that they are. Alot of the math community goes to this. There is a pamphlet of what the contributed talks will be (there are multiple parallel sessions) so you can pick and choose what to goto. Even though the contributed papers are not refereed, some of them are worth hearing Authors not forced to register.
3. Southeastern International Conference on Combinatorics, Graph Theory, and Computing. this is last years conference Similar to AMS meetings but more specialized. Registration about 200 dollars. (`Southeastern International' is oximoronic and makes it SOUND like a bogus conference, but at that price and no claim to refereeing, its fine.)

Going to a conference to meet people and see some results in the early stages, or to give you things to think about are valuable. Unrefereed conferences are NOT a good place to pad your resume (if your school knows about quality). If you get a paper into one you should clearly label it as UNREFEREED CONFERENCES on your resume.

As a community we seem to have lost the ability to have an informal meeting (exception: Dagstuhl and others like it, which are informal BUT you have to be invited to them.)

SO, what does make a conference bogus?

1. They CLAIM that its refereed and it is not.
2. They seem to be overcharging OR charging for very odd things.

Bogus or not- You decide

SO, is TMFCS08 bogus or not? First off, Bogus to me is not a matter of quality There are some unrefereed conferences I go to that I enjoy and get something out of. They also have LOW registration fees. Bogus means that they are putting it on soley to make money and are offering nothing intellectual in return. Of course, if enough good people goto a bogus conference then they will talk to each other, so maybe it is worth it. But it depends on the price.

I emailed Mike Sipser. Below is his response, which includes a response from the conference organizers. (I have edited it down a bit but have not changed the content. I also have one clarifying remark.)

Hi Bill, I'm sending you the response from one of the conference organizers. From what they say this practice occurs at other conferences. I believe the conference is a real one, though I don't directly know the primary individuals involved. My personal role has been minor, just answering a few emails and giving a little advice. -- Mike

(REMARK FROM BILL: THIS EMAIL BELOW IS FROM THE CONF ORGANIZER TO SOMEONE WHO GOT PAPERS IN AND INQUIRED ABOUT IT.)

From: Bhanu Prasad

Subject: Is TMFCS-08 a real conference?

This email is in response to your email sent to Prof. Sipser. Prof. Sipser asked me to look into this. Hence I am responding.

I learned that you submitted two papers and requested the conference people to conduct the review fast. They (conference people) have informed you the acceptance, along with the review results as soon as they received from the reviewers. Then you asked them to send the invoice for payment of fee using PayPal. They have sent it. Then you asked if the fee is for both the papers or for one paper. They informed that the fee is for one paper but they reduced the fee for the 2nd paper by 30%.

For your information, I am aware of several conferences where they do not even reduce the fee for the 2nd paper. See for example, http://conferences.computer.org/scc/2007/registr.html . They clearly indicated the following: "Each paper needs at least one FULL registration, before the camera-ready manuscript can be included in the proceedings. There is no student rate for the author who is responsible for registration for his/her published paper. If you have more than one accepted paper, you need to register for each one individually. There is no discount if you have two or more papers accepted."

For your information, it is a real conference (because the people in that are real and I was there in 2007 conference, and it will have proceedings, etc.).

I don't think a fake conference will become real just because they collect one fee for both the papers.

Best regards, Bhanu Prasad, Organizing committee

Theoretical and Mathematical Foundations of Bogosity

I recently got the following email.

I sent to papers to a conference TMFCS08 (Theoretical and Mathematical Foundations of Computer Science) and got accepted, however, they ask me to pay the registration fee twice, one for each paper (2x$550), is that normal?

1. I emailed her that this IS normal for bogus conferences that are complete ripoffs, but not normal otherwise.
2. I'm surprised anyone falls for this kind of thing. Then again, it may be that the school that the prof is at also does not know the difference, so it does help the resume.
3. I looked on the web for more info on this conference and could not find anything saying it was bogus (By contrast you can find stuff about WSEAS being bogus). Anyone have any more information?

Reading Math over Thanksgiving

What did I do over Thanksgiving? I read Ernie Croots's excellent exposition of Szemeredi's Regularity Lemma which is here

It is sometimes easier to learn stuff when you are AWAY from your computer. Less distractions. BUT if you need to look something up, its harder. BUT this may force you to think harder. BUT maybe you need to look something up and can't derive it yourself BUT, BUT, BUT... However, it worked this time.

I also came up with a trivial math problem based on real life. I got into an elevator that had 23 floors and was going to the 4th floor. Two people got in and BOTH pushed buttons that were LESS than the 4th floor and diff from each other. I later thought `Gee, you would think being on the 4th floor you wouldn't stop twice to get there. What is the probability of that happening?' I had the answer in about 1 minute. Much easier than understanding Szemeredi's Regularity lemma. ~

Advice about NSF grants (not from me)

How to get an NSF grant? If I knew I would have more Grant money. However, I was emailed the following powerpoint slides with the request to post them on my blog, so here they are

More on the Tables Problem

Recall the tables problem, which I now state more clearly than I did in my last post:

n couples go to a resturant. They will sit at a rectangular table that has room for n on each side. Each person sits either next to across from their darling. How many ways can they sit?

Most people got the correct answer in the comments on my last blog. But some other interesting points were raised that I will address.

1. I had commented that this was asked on the 2007 Maryland High School Math Olympiad, Part I,, problem 23, which is with Multiple Choice, for the case of n=5. Some commenter wanted to know what the choices were: 360, 768, 5040, 19200, 30720.
2. Someone commented that the problem `was not new' and gave this, problem 4, as a pointer to where it had been asked before. Here is the problem they were referring to:

   Define a domino to be a 1x2 rectangle. In how many ways can a nx2 rectangle be tiled by dominos?

   This raises an interesting question: When are two problems equivalent? Does phrasing matter (I had people, they have dominos)? Does making certain things distinguiable or not matter (Dominos are not distinguiable, couples are)? Does having different answers matter (his is Fib(n+1) mine is a Fib(n+1) x 2^n x n!)? More generally, its not clear when a problem is new.
3. Just to reiterate- there is math all around you if you know where to look.

Math Problems from everyday life

Often I see something in real life that inspires a math problem. Could be a math problem for an exam or a student project or (more rarely) serious research. (e.g., I give my 9 year old great nephew seven crayons and he colors the numbers 1,...,2000 without any monochromatic 3-AP's so I get a new VDW number out of it.)

Here is one that inspired a problem that ended up on the Maryland Math Olympiad, Part I (which is 25 multiple choices questions). (5 choices, 4 points for a correct answer, 2 points for a wrong answer. You really really do not want to guess.)

Here is what happened: I went to dinner with my darling, and my two sister-in-laws and their husbands. I sat across from my darling but the other couples sat next to each other. So here is the question: I immediately thought about the following question:

$n$ couples go to dinner. They sit at a rectangular table, but nobody sits at the ends. Each couple either sits ACROSS FROM or NEXT TO their darling. How many ways can they be seated?

The problem on the exam was asked for 5 couples and gave choices.

Its not a hard problem for the readers of this blog, so I leave it to my commenters to solve it. (If nobody does I'll post the solution later.) Note that it would be hard for a high school student- very few got it correct. (We suspected this would be the case. We try to order the questions by difficulty and this was question 23.)

COMPUTATIONAL COMPLEXITY CONF 2008 SUBMISSIONS WEBSITE OPEN!

Computational Complexity Conference 2008 (CCC 2008) submissions website is now open: go here for submissions website or go here for more info on the conference

1. Submission deadline is Dec 6, 2007, 17:59 PST
2. Notification will be by Feb 8, 2008.
3. Conference will be in College Park Maryland (details on that will be on the conference website soon)
4. It will be awesome!

Trivial question: Name everyone who has been to every single COMPLEXITY conference, including when it as called STRUCTURES? (I've been to all but one, Jack Lutz has been to all but two, so we do not qualify.)

Richard Beigel is at NSF

Richard Beigel is now one of five Program Director at NSF for CISE/CCS/TF (TF= Theoretical Foundations) This is the job previously held by William Steiger (who will stay on part time for two months, but is already back at Rutgers.)

Lets all wish him well on the job- if he does well, we do well.

Resubmitting Rejected FOCS paper to STOC

(Guest post by Kamal Jain Resubmitting the rejected papers from FOCS to STOC?

If your paper was rejected by FOCS and you're submitting it to STOC, here are my thoughts on how you can increase your chances of acceptance. Given the low acceptance rate for FOCS, I am sure many of us will be resubmitting our rejected papers to STOC. Many of us will be incorporating the FOCS PC comments. And there's also a realistic chance that FOCS PC misunderstood our papers. So what should we do so that STOC committee does not repeat the misunderstanding?

Let me first describe the general methods to contain the chances of misunderstanding. I will then describe why the chance of misunderstanding has increased for STOC PC on resubmitted papers by giving you an insider view of FOCS 2007 PC. We can then discuss what we could do to minimize that.

Contain the chances of misunderstanding

Well of course removing the items from the paper which gave rise to misunderstanding could be beneficial. These items could arise either due to lack of explanation, positioning of clarification, or overselling the results. Lack of explanation happens because we fail to realize as authors that our mind is pre-conditioned while researching on the paper and the reviewer's mind won't be pre-conditioned in the same way. Therefore things which look clear to us may be confusing to a reviewer. Positioning of clarification is very important because not every paper is read word to word. So it is very important to put the clarification or a pointer to it as close as possible to the place where confusion could potentially arise. Overselling does not improve the chances of a paper getting accepted. Overselling of results typically puts the reviewer in a defensive position. A reviewer could look at other existing papers that have introduced similar techniques and be at a loss for what is new, unique, and real about what this paper promises.

So how do you address these problems? One thing is to prepare the paper early and seek feedback. Do not expect somebody, who is not genuinely interested in your work, to provide you good quality feedback for free. You would need to pay. How? Offer the same high quality service on their papers as you expect on your own papers. Posting your papers online, e.g., as a technical report in some archive could also bring some early readership, which may provide you feedback and opportunities to exchange feedback.

If you really need to sell your paper, what's the best way? Give talks -- as many as possible. Try to accept every invitation and try to get yourself invited by marketing the results. In order to market the paper be open to discussing your results in small chats without pen and paper, e.g., over a lunch table. Acknowledge all pre-publication discussions, including those which were not explicitly used in the paper. Mentioning the names of the people is very important, and in case of explicit usefulness, mentioning it explicitly is equally important too. This is so that your colleagues feel acknowledged and positively reinforced to collaborate with you in the future. In the short term, these colleagues are also likely to see the papers more positively vs the case if they find their assistance is not fully acknowledged.

What else can you do if you do not yet have enough opportunities to talk about your paper? We have not done so, but there are cheap as well as free software using which we can easily make a high quality screencast. For me personally, a high quality screencast provides 80% of the benefit of watching the talk in person. Much of the benefit of the remaining 20% can also be obtained if there is an open forum associated with the screencast to ask questions which can either be answered by the authors or other viewers in a relatively short time. Readers do not have the patience unless they are genuinely interested in your result. And expect to count the number of the latter on your fingers.:)

An insider's view of FOCS:

What's specific about paper reviewing these days? As part of the FOCS committee we had access to reviews submitted by the previous STOC committee. We paid a great deal of attention to whether the version we had had responded to the STOC PC's reasons of rejecting the papers. Similarly expect STOC 2008 PC to have FOCS 2007 PC's reviews available. The intersection between STOC 2008 PC and FOCS 2007 PC is non-empty. Even if you think FOCS PC misunderstood your paper, and responding to those misunderstandings would make the paper less readable, you should still try to respond to those misunderstandings instead of ignoring them. In such cases you can respond to those misunderstandings either in appropriate footnotes or in a one page appendix in the end. If your footnotes and appendix are just for STOC PC, do mention "for the reviewers only, will be removed from the published version."

What about the feedback that FOCS PC kept confidential and did not transmit to the authors? This part of the feedback must not be used by STOC committee for three reasons. First, it was understood that only FOCS PC share that feedback. Second, this part of the feedback was a part of the process and not the net outcome. The net outcome ideally must be included in the "send to author" part of the feedback. Third, since this part of the feedback was not transmitted to the authors, they can't be expected to respond. If this part of the feedback did contain a reason why the paper should be rejected then authors must be sent the reason. If this was not done in some cases, then STOC PC must work hard to rediscover the same reason for rejection.

This is my view from both having submitted (and received rejections) papers as well as been part of various PCs. I hope these give you additional practical tical tips on how to best position your papers. I welcome other ideas so that we could continue to improve the quality of our submissions.

Thanks,

Kamal Jain.

Note: FOCS means FOCS 2007. STOC means STOC 2008. Previous STOC means STOC = 2007.

It was a stupid question!!!!!!!!!! or...

On my last blog I asked the following: TRUE OR FALSE:

For every coloring of R (the reals) with a countable number of colors there exists x,y,z,w of the same color such that x+y=z+w.

And I pointed out that when I asked this in seminar I got 5 thought it was TRUE, 4 thought it was FALSE, 5 thought it was a STUPID QUESTION.

The answer is: ITS A STUPID QUESTION. More rigorously the following is true and was proven by Erdos:

The statment above is true iff the Continuum Hypothesis is false. (See this (pdf) or this (ps). for an exposition of the proof.

SO, what to make of this? This is a natural question that is ind of ZFC. How Natural is it? Erdos worked on it, not some logician looking around for a problem to be ind of ZFC.

Does this make us think CH is true or false? Actually, more is known:

Let L(x₁,..., x_n) be a linear form over the reals (but not x₁-x₂). If CH is true then there is a coloring of the reals with a countable number of colors such that there is no e₁,..., e_n which are all the same color such that L(e₁,..., e_n)=0. (Exposition of proof in same document linked to above.)

If CH is true then the entire theory of countable colorings and linear forms is known. And boring. If CH is false then much more interesting things happen. Jacob Fox proved the following:

Let STAT(s) be the statement

For every coloring of R with a countable number of colors there exists x₁, x₂, ..., x_{s+3} such that they are all the same color, and x₁ + sx₂ = x₃ + x₄ + ... + x_{s+3}

THEN STAT(s) is true iff 2^ℵ₀ > ℵ_s

Jacob Fox is also (judging from his resume) not a logician. He is a combinatorist. Actually he's a graduate student so it may be too early to say what he is.

To determine CH should we use its consequences as reasons for or against assuming it? Even if we do, do you want the entire theory to be known and boring? I ask this non-rhetorically. See Opinion 68 of Zeilberg's blog or The papers of Penelope Maddy: believing the axioms I. and believing the axioms II.

Equations and Colorings: Rado's theorem

Is the following TRUE or FALSE?

For every 17-coloring of N (the naturals- not including 0) there exists x, y, z such that x,y,z are distinct x,y,z that are same color such that 2x+3x-6z = 0

It turns out that this is FALSE. We'll call a set b₁,...,b_n REGULAR if

for every c, for every c-coloring of N, there exists x₁,....,x_n such that x₁,....,x_n are all the same color, and b₁x₁ + ... + b_nx_n = 0

The following is known as (abridged) Rado's Theorem. Rado proved it in 1933.

(b₁,...,b_n) is regular iff some nonempty subset of the b_i's sum to 0.

For an exposition of the proof see Ramsey Theory by Graham, Rothchild,and Spencer or see my writeup
NOW- here is a question to which the answer is known, and I'll tell you the answer in my next post.

TRUE OR FALSE:

For every coloring of R (the reals) with a countable number of colors there exists distinct x,y,z,w x,y,z,w same color x+y=z+w.

When I asked this in seminar I got

1. 5 thought it was TRUE
2. 4 thought it was FALSE
3. 5 thought it was a STUPID QUESTION.

Do we root for how a problem will go?

When you are working on a problem do you have a rooting interest in which way it goes? Sometimes yes, sometimes no. A story:

A 3-free set is a set with no arithmetic progressions of length 3. Large 3-free sets of {1,...,n } were used in the best known Matrix Multiplication algorithm. It is known that there are such sets of size n^1-o(1) but there cannot be such sets of size &Omega(n) (slight tighter results are known).

I was finishing up a paper on large 3-free sets. The paper was not about applying these to anything; however, there was a short sections that mentioned some applications. I needed to know, just for some refs and background knowledge, if larger 3-free sets would lead to better Matrix Multiplication algorithms. So I emailed some people involved with Matrix Mult and one of them, Robert Kleinberg, responded. To paraphase the emails back and fourth he said the following (italics are mine):

The known algorithm uses that there are 3-free sets of {1,...,n} of size n^{1-o(1)}. Improvements to the current constructions of large 3-free sets will not help matrix mult algorithms. To improve matrix mult algorithms you need sets with more complicated conditions on them. Sorry the answer is not what you wanted it to be

Actually I was happy to know this. I did not really have a rooting interest. Do we root for a result do go a certain way? Do we want to see P=NP (better algorithms) or P\ne NP (better crypto)? (I'd go for better algorithms and let the crypto people find other problems to base systems on- some of which I think has already happened.) Do we want to see P=BPP (confirm our current intuition) or P\ne BPP (confirm our 1980 intuition)? Do we want to see GI\in P or GI \notin P? Do we want to see PH collapse or not collapse? Do we have a rooting interest in any of these problems?

I would think algorithms people root for finding faster algorithms rather than showing a problem is NP complete. Complexity people are happy to either seperate or collapse classes. If only we do it more often.

Stoc seeking papers that...

STOC deadline is coming up and the organizers have asked me to publicize a particular aspect of it. Note that in the call for papers it says: Papers that broaden the reach of theory, or raise important problems that can benefit from theoretical investigation and analysis, are encouraged

Since I was explicitly asked to publicize this, I assume they really mean it.

Submision Deadline: 7:59PM, EST, Nov 19.

THANKS to Nicole's FOCS blogs and her positive outlook

I want to extend a warm thanks to Nicole Immorlica for Guest blogging from FOCS. So I will:

THANK YOU NICOLE!

(Would have done this yesterday but if I had delayed getting the WOLFRAM PRIZE information out there I would have gotten at least 10 more emails telling me to post it.)

The one thing that struck me the most about Nicoles FOCS blogs is the positive outlook usually missing from discussions about theory. If you look at this blog, other blogs, or just talk to people in theory, you usually read or hear negative comments like these:

1. FOCS is biased
2. STOC is too expensive
3. Theory is underfunded
4. Australian actresses are plagiarizing my quantum mechanics lectures to sell printers.
5. Back in the good old days people worked on important problems. Now they just get incremental results.
6. Bring back Lance!

Some of these complaints are certainly valid. But hearing or reading such negativism can be monotonous, and blind us to some positive developments. Hence I appreciate Nicole's positive outlook on FOCS and Theory in general. I hope it lasts her entire career.

Wolfram Prize won!- There IS a (2,3)-UTM

Recall that the Wolfram Prize which I blogged about here, was given to anyone who can determine if a certain Turing Machine was universal. It is now known that YES that machine IS universal.

Congrads to Stuart Kurtz, Lance Fortnow, and Kathryn Cramer, Jon Katz, and Katrina LaCurts- NOT for winning the prize but for being the first ones to tell me who won the prize so I could post it. For that they win... a mention in this blog.

Here are some websites about it, most of them emailed to me by Kathryn Cramer.

1. write up in nature
2. Stephen Wolfram's blog!
3. Smith's 44 page proof!
4. New Scientist Story
5. Alex Smith's Photo!
6. Geomblog scooped me here
7. Live Journal

BACK TO BILL:

How important is the result? Alex Smith got $25,000 for it. The market has spoken, the result is important.

FOCS VIII

Nicole's final FOCS post.

And it's over! The 48th FOCS ended at 6.10pm with a talk on "The Computational Hardness of Estimating Edit Distance". About 50 brave souls lasted the whole three days.

Overall it was a really great FOCS. The results were good. The company was good. I have to admit, even the food was generally pretty good!

See you all next spring at STOC in Victoria.

FOCS VII : Funding? NSF? whats it all about?

(Another Guest post from Nicole!) More from the Business Meeting

Funding status report: I'm not really the right person to blog about funding since I have never yet applied for a grant. From the business meeting, it seems like a lot of people are doing a lot of hard work to funnel more of the NSF budget into our hands. They seem to have had some success. There are two new initiatives -- CDI, Expeditions -- and several old ones which now have more money than before -- ToC, SING. Funding rates seem to be around 25% (33% for CAREER). (An aside, maybe we should also try in an organized way to funnel more of the federal budget into the NSF by, e.g., writing our representatives in congress -- you don't have to be a citizen to do this -- or through PR campaigns.)

But you can find all this info on the NSF website. What you can't find on the NSF website is how it affects us young academics. I am about to start my first faculty job, and funding has suddenly become a very real issue for me. I see these numbers, I hear about these politics, and I am totally in the dark. I have never written a proposal, never even read a proposal. I don't know how to play the game. I know my senior colleagues will help me through this process, but that does not reduce the anxiety. I suppose every career path has rites of passage like these. The thing is some rites of passage are fun. I could be wrong, but I'm not looking forward to this one. ~

FOCS VI- Local Arrangements AND the future of FOCS!

(Another Guest post from Nicole!)

The business meeting was fun thanks to Mihai!

Local arrangements: First, let me say how wonderful the local arrangements were this year, a sentiment I've heard from many others here. Thanks so much for making this FOCS happen.

Claire gave a very detailed account of the local arrangements. The general message seemed to be that things are expensive. Expenditures this year reached $100K. The usual culprits were at fault -- food ($265 per person, total of $66,000), paper proceedings ($32 per person, total of $11,700), PC meeting/registration fees ($12,000), room/equipment rental ($4,200). Everything sunk in when it was announced that we're looking at a $525 registration fee for STOC 2008 in Victoria, admittedly thanks in part to the falling dollar.

The usual debates ensued -- paper vs CD vs online proceedings, catered lunch vs on-your-own, alternate conference venues. Let me capitalize on my journalistic duties to further my personal opinion on these matters: online proceedings (and ideally someday online PC meetings) are much more environmentally friendly. For me, this is enough. But, besides environmental and monetary costs, online proceedings are also easier to access after the meeting and can include media beyond print, e.g. slide presentations, videos of talks, etc. (see, for example, the excellent wiki of FOCS 06 built by Amin Saberi). People who really want paper proceedings can go to Kinko's with a printout of all the papers and pay $50 to bind them.

But honestly, I'm getting tired of this annual debate. Let's just do it my way. ;)

FOCS V- Report from Prog Comm.

Another great guest post from Nicole Nicole Immorlica, from FOCS

(Note from Bill G: This is one of several posts Nicole will be making from the Business meeting.)

Program committee report: Another congrats is in order. No matter what you think about the distribution of topics (see below), you can't deny that the PC did a great job this year. I was especially impressed by the extensive feedback, both internal and external, on submissions; the comments were thorough and explicitly stated the PCs reasons for their decision. Now for the statistics, well, here's the list that was presented at the business meeting: The number of submissions: 302. The number of accepts: 66. Below is a topic that there were papers submitted on, followed by how many submitted,and how many accepted.

1. Algebraic/Numerical Computation (14, 1)
2. Algorithmic Game Theory (27, 5)
3. Algorithms 85
   1. Approximation (35, 9)
   2. Geometric (8, 2)
   3. Graph (17, 1)
   4. Randomized (14, 4)
   5. Streaming (6, 2)
   6. Misc. (15, 0)
4. Combinatorics (2, 0)
5. Computational Biology (2, 0)
6. Computational Complexity (30, 14)
7. Cryptography (20, 7)
8. Data Structures (6, 2)
9. Geometry (13, 3)
10. Learning (7, 0)
11. Logic/Proof Complexity (11, 2)
12. Parallel/Distributed Computation (15, 1)
13. Property Testing (10, 5)
14. Quantum Computing/Crypto (25, 6)
15. Random Structures (7, 2)
16. Misc. (11, 0)
17. Out of Scope (6, 0)
18. P = NP (1, 0)

I think I'll leave it up to the commentators to interpret this.

FOCS IV

(Even More from Nicole Immorlica, guest-posting from FOCS. This post is from Oct 22, 7:00PM)

I remember taking writing classes in high school. We had a series of assignments emphasizing different writing techniques and topics. But each assignment started with the same question, the question which set the tone for the entire piece of work. Who is your audience? The importance of this question was the most valuable lesson I learned in those classes.

I've now attended about a quarter of the FOCS talks -- all the ones close to my area and a smattering of those completely outside my area -- and it seems to me that there are two types of audiences in every talk. There are the locals, those that are intimately familiar with the research area of the talk; and there are the tourists, those that want to explore something new.

How do you speak to such an audience? Most speakers seem to split the talk into two parts: accessible introduction/overview/problem statement and area-specific implications/proof techniques. And then they have to pack it all into 20 minutes. The result? Minds wander. What can be done about this? Longer talks to allow for a smoother ramp-up to the technical details (and hence fewer papers overall)? Parallel sessions (something FOCS has toyed with in the past)? Or maybe nothing? As my grandmother used to say, "you can please all of the people some of the time and some of the people all of the time but never all of the people all of the time."

FOCS III

More from Nicole Immorlica from FOCS.

The first day of FOCS is over. The highlight of the afternoon was the talk by Nancy Lynch, winner of the Knuth Prize. She began with, as one attendee put it, a nostalgic synopsis of FOCS/STOC from her first Denver 1972 conference in a cheap hotel across from a dirty movie theater on through the splintering of theory and distributed computing in the 80s. She then launched into a very accessible description of her famous paper on the impossibility of distributed consensus. The talk ended with an overview of current and future work in the field.

I think everyone in the audience was pretty satisfied with her outlined research agenda involving models of distributed computing on mobile networks until the air traffic controller example. She primed us by suggesting that her research could replace traffic lights with virtual traffic lights, which made me tense up slightly. Then she suggested we could even replace human air traffic controllers with virtual ones. While we all understand the benefits (e.g., you can have controllers over the ocean, machines don't get tired, etc.), I think we all had a sort of collective gasp. I guess at the end of the day, I just want to know there's a human behind it all, attentive and directly in charge.

One more thing I think is worth mentioning – this is the first Knuth prize (out of 8) awarded to a woman. This same year was the first year (out of 41) that a woman, Fran Allen, won the Turing award. This trend is both alarming (it took 41 years?) and encouraging (ample research and personal experience demonstrates the significance of female role models for professional women). Congratulations and my sincere gratitude to you both for paving the way.

FOCS II

Nicole Immorlica continues to blog from FOCS.

Just finished the morning sessions of day one. I guess it's time for the standard disclaimer – the talks I blog about are those I happened to attend and should not be interpreted as the "best" or even my personal "favorite" results, etc. etc. etc.

So about the sessions. Session one started at 8.30 AM and I'm embarrassed to admit that despite being the "guest blogger" of FOCS I missed the first talk. Somehow research before 9.00 AM is akin to hard liquor before breakfast for me. I just can't stomach it. I caught the end of the talk though, and was shocked that the room was packed! I took a picture, try and see who isn't there. :)

The second session was much closer to my research area – algorithmic game theory – and hence I got much more from those talks. One particular nice result was that from the paper Mechanism Design via Differential Privacy. The authors introduce a new solution concept for mechanism design which resolves many of our frustrations with dominant strategy mechanism design, and they do so through a creative connection to a seemingly unrelated field – privacy.

FOCS I

Nicole Immorlica guest posts from FOCS.

I wake up bleary-eyed and jet-lagged at 6 AM begging of myself WHY? Why do I subject my body to such torturous trans-atlantic flight for three days of, of what? Of talks of which I will attend at most a quarter? Of hotel banquet food? Of aching back muscles from lugging around massive proceedings and laptops bundled together in free canvas tote bags that I don't really want anyway?

For me, the answer is the people, my friends, my colleagues, their quirky interests and insightful comments. It's the research in the corridors, the animated technical arguments over the lunch tables, the great stories that get told by a diverse set of people from a diverse set of backgrounds.

Basically, it's like a big family reunion. But families you are born into. How do you get born into the FOCS family? I remember my first FOCS – Las Vegas 2001 – feeling alone, isolated, shy. Now I feel a part of the family, accepted into this community due in part to my papers, yes, but also labels that were really a matter of luck. What becomes of all those people that didn't have my luck?

Why do I find this result interesting- MOD 17 SAT

I find the following result to be really interesting but can't quite say why: (For this exposition ≤_m means poly-m-reduction)

Let SAT₁₇ be the set of formulas such that the number of satisfying assignments is a multiple of 17.

If SAT₁₇ ≤_m S, S sparse, then SAT₁₇ ∈ P.

This is one of those results where the proof in the literature is hard because they prove something far more powerful (btt reductions- and more). Hence I have my own exposition that I made for my class here.

I presented it in class recently and the students questioned why it was interesting. I can usually answer questions like this (even about such things as the Polynomial VDW theorem) but this one is harder to say. I DO find it interesting (not just the proof, but the result) but can't quite say why.

SO, here is my challenge: either tell me a reason the result is interesting OR tell me a result that YOU find interesting but can't quite say why.

A more intelligent SPAM discussion

I wish to start a more intelligent discussion of spam then my last post lead to (my fault). And YES, the story I pointed to was a hoax.

Is Spam a big problem? I contend that it is and that it is going to get worse. Some random thoughts, some of which are what to do about it.

1. Make it illegal or make the penalties tougher. I don't know what the current legal status is, but even with tough laws this is hard to enforce because (1) What is spam? and (2) it would require international cooperation.
2. We could try just making spam that is trying to rip you off illegal. I'm sure it is. But sometimes its hard to tell what is a rip off and what is not. The ``Nigerian Billionaire'' scam is clearly a ripoff (does anyone still fall for that?) but the ``you can get viagra at a cheap price'' might not be. The ``we can get you out of debt'' is much harder to judge since (from what I understand) they pay your debts, charge you an enormous interest, but let you pay it off over a much longer period of time. It may well be legal but unethical. It may even be legal and ethical.
3. Keep designing better software to block spam. This is the current solution, and it works pretty well, but its getting harder, and too much real email is being blocked. Also, this is more of why I think its a big problem- we (as a society) spend an awful lot of time and effort on this.
4. As more people know that these are scams and less people fall for them, will the scam-spams stop? Can we educate people so they know better?
5. Fighting back- there was an article in the Atlantic Monthly about people who scam the scammers- with success. But there are not enough of them, and they are not that effective, to be a real deterrent.

So there are essentially legal, technical, and educational solutions. Are there others? (NOT including assasination.) Can they work? Who is winning this war? How can we tell?

Spam Assassin

In Russia a notorious spammer was assassinated

Is this a crime? Should it be? Consider the contrast:

1. Killing one person. How many people suffer and how much? The victim of course. Maybe his family and friends. But not that many people. So this is High Impact on a Few People.
2. Spamming 100,000,000 people. How many people suffer and how much? Far more than 100,000,000 suffer. Why so many? The following suffer:
   1. Software is more expensive because you need to put in spamassassin's.
   2. People who send legit email that is blocked. This has caused confusion not worthy of a bad sitcom.
   3. The people who fall for these spam-scams.
   4. The Nigerian billionaires who really do want to give me $5,800,000 dollars. Its hard to tell the real ones from the fake ones.

So, how to measure the cost-benefit of killing this spammer?

{ s₁, s₂, ..., s_n } is the people that suffer by the spammers death. Person s_i suffers a_i.

{ t₁, t₂, ..., t_N } is the people that suffer by the spammers action. Person t_i suffers b_i.

Its safe to assume that n is MUCH LESS THAN N and that b_i is MUCH LESS THAN a_i. If

a₁ + a₂ + a₃ + ... + a_n < b₁ + b₂ + b₃ + ... + b_N

then the spam assassin should not be charged with a crime.

The more serious question here is how to deal with spammers who transcend boundaries and seem outside of the law. The Russians may be onto a solution...

Is Computer Science a Science?

Is Mathematics a Science? Is Computer Science a Science (hmmm- it has to be, its in the name :-) )? Is Richard Stallman a computer scientist? How about Bill Gates? How about my wife who has a job programming? For a serious discussion of some of these issues see an blog of Lance's For a less serious discussion, I offer the following thoughts.

1. Calling something science, engineering, art, or business is not an insult or a compliment.
2. A topic is a science if it has a lab where there is the potential for danger. Physics has radiation, Chemistry has explotions, Biology has germs. So they are sciences. Neither Math nor Computer Science has those.
3. Hence, asking if Richard Stallman is a computer scientist is not really a question. So perhaps we need a different term. `Computer Programmer' is a fine term and we know what it means. How about if we call ourselves `Computer non-programmers'? Depends if you consider LaTeX a programming language (it is Turing-Complete).