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).

The Free Software Foundation and Richard Stallman

Richard Stallman gave a talk at University of Maryland at College Park. He is the head of the free software foundation. The terminology `free software' does not mean that software should be given out for free. It means that once you buy software you should have the right to use, study, copy, modify, and redistribute it as much as you like. EMACS, which he wrote, has this kind of license. So does GNU which is an FSF project. The talk was pretty good. He made some valid points about the evils of the current system. I think he has some good points to make.

1. He talked for 1 hour 45 minutes. This is probably 45 minutes too long.
2. When I say he talked for 1 hour 45 minutes I am being literal- no slides, no blackboard presentation, just talking. This may be because to use technology he would have had to use Software from a company that he does not approve of.
3. He speaks of free software as a human right. He speaks of it as the worst evil in the world. There are worse evils in the world; however, all good causes need true believers, and he is one.

I've heard all this before and further ago than most people. In 1982 he was my housemate in Graduate School. He had some of these ideas then, but they are better develped now. I sortof wish I had gotten involved with Free-Software early on since its a good cause and it would be nice to be able to contribute to society in this way.

P.S. Richard Stallman is not the most famous computer scientist who knows me. Serge Brin, co-founder of Google, had two courses from me as an Undergraduate. I definitly wish I had gotten involved with Google early early on since its a good product and it would be nice to be able to contribute to my bank account in this way.

If pigs could fly then bacon would be cheaper

Pretend you didn't know the Karp-Lipton theorem. Consider the following two statements

SAT has poly size circuits.

The Poly Hierarchy collapses.

You probably think both are false. Which statements truth would surprise you more? Personally I think SAT has poly size circuits would surprise me more.

Karp-Lipton Theorem:

If SAT has poly size circuits then Poly Hierarchy Collapses.

Does this really make your belief that SAT does not have poly sized circuits stronger? You already believed that. I know of one theorists who tells me that she believes SAT does not have poly sized circuits MUCH MORE than she believes that PH does not collapse. Hence this theorem does not tell her anything.

If you have

(unbelievable statement A) --> (unbelievable statement B)

what do we then know that we didn't know before? We know that A is MORE unbelievable than B, I suppose. We seem to have taken

BLAH --> P=NP

as the gold standard in showing that we believe BLAH is false and

BLAH --> PH=\Sigma_2^p

BLAH --> PH=\Sigma_2^p

etc. as forming a hierarchy of non-belief.

This is a nice picture, but it may be that BLAH is just not that believable in its own right and does not need to imply something like $\PH = \Sigma_3^p$ to give NOT(BLAH) street cred.

Deal-No Deal: MORE $ = LESS Interesting

I caught an episode of DEAL-NO DEAL recently (see this for a description). The math behind this game has been described in blog postings of Lance (see this as well as the above link)

The episode I saw showed something wrong (at least in my opinion) with the way they are promoting the show during premiere week. They have upped the amount of money to be a max of $4,000,000 (instead of $1,000,000). I saw the following (this might not be quite accurate but makes the point) There were 6 numbers left:

1. $5,000
2. $10,000
3. $20,000
4. $100,000
5. $1,000,000
6. $4,000,000

and the bankers offer was $700,000. $700,000 is so large and so life changing that the decision to take it (which she did) is rather obvious. Even the audience WAS NOT yelling `NO DEAL! NO DEAL!' like they usually do. To exaggerate this, imagine if the top amount was $40,000,000 and your dilemma was whether to take $7,000,000 or risk it to maybe do alot better but maybe do alot worse. YOU WOULD TAKE THE $7,000,000. (or at least I would).

A question like `would you take $70,000 or take the chance that you get $400,000' is mildly interesting. But the $700,000 is to large to not take. Hence the game gets less interesting mathemtatically.

Given a persons utility function (or something like it) what would be the optimal max amount (and optimal set of amounts) to maximize the games INTEREST? This question might be interesting.

WHERE to apply to grad school?

Its the time of year when Seniors who want to go to Graduate School should be pondering WHERE to go. There are other issues which I will address in later posts, but

Today's topic is WHERE TO APPLY?

I would like YOU (the readers, and time magazines MAN OF THE YEAR for 2006) to comment on:

1. IF a student wants to do COMPLEXITY THEORY where should she go?
2. IF a student wants to do COMBINATORICS (in a math dept) where should he go?
3. IF a student wants to do XXX (in a YYY dept) where should ZZZ go?

Note that there may be lesser-well known schools (e.g., not on someone's arbitrary top 10 ranking) that are really good in these topics, and they should not be overlooked.

Andrej (Andrey) Muchnik-a late memorial

(Guest Post by Alexander Shen. Thanks to Lance for Suggesting it.)

Andrej (Andrey) Muchnik died unexpectly last March, but the news didn't spread out, so I am thankful to Lance Fortnow and Bill Gasarch who give me the opportunity to write a few words about him. His death was a sudden blow not only for his family (his parents, Albert A. Muchnik, of Muchnik - Friedberg solution of Post problem, and Nadezhda M. Ermolaeva; both were students of Petr S. Novikov; and his brother Ilya) but also for all his colleagues.

Andrej, whom I knew since our undergraduate studies, was not only the brilliant mathematician, but a deep thinker. He lived in his own world -- a very rich one that was not completely unrelated to a "real life" (i.e., the mess around us), but still clearly separated from it, and the interactions between these two worlds were quite difficult and often painful. His mathematical interests were driven by internal logic of the subject, not the current "fashion"; sometimes he rediscovered an old result not knowing about it; at some other times his results (being not published or published only in a short note) were rediscovered later by others. Probably his most known result is an elementary proof of Rabin's theorem (decidability of second-order monadic theory of two successors), invented while Andrej was a fourth-year student, and its generalizations; my personal favourite is one of his last results saying that for any strings A and B there is a string C such that |C| [length] is about K (A|B) [conditional Kolmogorov complexity]; K(C|A) is negligible and K (A|B,C) is negligible (all up to logarithmic terms).

a seminar in Moscow that was started by Kolmogorov himself; the work of this seminar and its participants was deeply influenced by Andrej, and I think that all we agree that most non-trivial ideas discussed in this seminar and most interesting results obtained by the participants of the seminar were due to Andrej (or at least inspired by him). Personally I am extremely grateful to him for all his support and encouragement and very sorry that I didn't tell this to him explicitly and didn't help him enough while he was alive.

See the seminar site note (both Russian and English) (written mostly by Andrej's teacher and friend, how helped him a lot, Alexey Semenov)

some papers of Andrej (not all -- we are still trying to prepare some unfinished papers for publication) can be found here

The Amish and Cell Phones

As most people know the Amish avoid using certain technologies. They think that some technologies are disruptive to the community. In the past the Bishops would meet and decide if a certain technology is okay to use. They do not use electricity over wires, but batteries are okay. However note that with electric wires or phone wires or cars (which need roads) the Amish Bishops can enforce their decisions. Not so anymore.

A long time ago they banned phones. They later made some allowances for having a phone booth for emergencies, but no phones in the house, for it would disrupt family time (the ultimate DO-NOT-CALL list). But more and more Amish are doing business with the outside world and as such phones are needed. More and more of them are using Cell phones (see Look whose talking).

I do not think Cell Phones are the real issue here. The real issue is that we now have technologies that an individual can use without the permision of the community. We also have dual-use technologies, so rules like `you can use it for business but not for entertainment or gossip' may be hard to control.

I was told by an Amish Man that the Bishops have ruled against Cell Phones and computers. But as batteries get better (and most of them have contacts on the outside who can recharge for them) I'll be curious how well this holds up. Will the authority of the bishops and the desire to hold the community together be enough to make the rules self-enforcing?

Math on TV

There was an episode of NUMB3RS (which starts its fourth season next Friday) that mentioned the the Kruskal Count (See also this link) This is a card trick invented by Martin Kruskal. His son Clyde Kruskal is in my dept. Martin passed away in late December of 2006 and it is likely they put that reference in as a tribute. (See this and this for comments on the memorial service.) I watched the episode with Clyde. The good news is that YES, they did indeed mention The Kruskal Count and thats kind of cool seeing someone you know mentioned on NUMB3RS. The bad news is that the reference made no sense whatsoever. Here are two items that make as much sense as what they said.

1. The list of suspects looks random but we know that its not. To solve the case we use the Nisan-Wigderson derandomization technique.
2. We know the murder took place within this 5 block by 5 block area. We know that there were 10 people interacting to plan it. We can solve the case by looking at both the space and the interactions and then applying the Lund-Fortnow-Karloff-Nisan theorem that changes space into interactions.

If math you did was on a TV show, would you mind if they got it completely wrong? Personally, I would not mind that, I would be delighted (and surprised) to find my name on TV. A bigger issue- if it was a bad episode I really would not like that since I would probably want to show it to friends and family, and I would not want to subject them to bad TV. (The episode of NUMB3RS with Kruskal Counts was a terrible episode.) SUGGESTION: Take some math that you have done and see if you can find a way to make it fit into an episode of NUMB3RS It does not have to make sense, but it should sound like it does. (As I did above.)

Is Immunity Interesting?

In my graduate complexity class I proved

For all computable T there exists a decidable set A such that A ¬in DTIME(T(n)).

I then had on the homework

For all computable T there exists a decidable set A such that, for all Turing Machines M that run in T(n) time there exists an infinite number of strings x such that A(x) &ne M(x)

I then had extra credit

For all computable T there exists a decidable set A such that, for all Turing Machines M that decide A, for almost all inputs x, M(x) takes more than T(|x|) steps.

Katrina LaCurts, one of my students (who is thrilled to be mentioned by name in this blog!) asked the following: Is the HW and Extra Credit just to reinforce knowledge OR is the notion of differing infinitly often an important topic within complexity theory?

How important is the notion of sets differing infinitly often? A quick-and-dirty measure is to find the number of papers on this topic. A quick-and-ditry way to do that is to grep `immunity' in Joel Seifras's Theory Database and then edit. Once done I get the following list

So I could answer Katrina, there are at least 21 papers on this topic That shows people have worked on it (and some quite recently) but does not quite answer the question. Hence I ask my readers:

Once we have that, for all time bounds T, there is a computable set A ¬in DTIME(T(n)), why do we care about getting an A that differ infinitely often, or other variants? More generally, why is the notion of having two sets differ infinitely often important. I ask non-rhetorically and politely. Note that, no matter how you answer, Katrina still has to do the HW.

Question and Metaquestion about Students emailing you problems

I recently got an email that said roughly the following:

Hi Bill,
I am a grad student in combinatorial optimization, and I have a question that I was hoping you could answer: does "FOO is APX-complete" imply "FOO is MAX SNP-complete", vice-versa, or neither?
To be honest this might be very simple... but given that this is essentially the domain of computational complexity I was hoping that either you would know the answer, or otherwise that your blog's readers might have some suggestions. (Basically your blog is currently the main source of computational complexity to my brain, so it seemed natural to ask you when I became confused.)
My impressions from reading up are the following:

1. APX is the subset of NP optimization problems with constant-factor polytime approximations
2. MAX SNP has a much more complicated definition
3. APX contains MAX SNP but I don't know if the containment is known to be strict

To motivate my question, many papers say "the FOO problem is MAX SNP-hard and also APX-hard" but is there currently a point in stating both? As I researched the topic, I found that the reductions allowed in the definition of "APX-hard" and "MAX SNP-hard" are apparently slightly different... and around here my confusion set in.
One compendium, at least, uses simply "APX-hard" by convention: here
I hope this is up your alley, but if not then no worries.

Sincerely,

NAME DELETED FOR THIS BLOG POSTING

This email raises several questions and metaquestions

1. The question on APX might be interesting.
2. Is this a HW question? Is she cheating on it by asking me? Should I answer it? My inclination on this one is that its NOT a HW, it is legit. However, I don't know the answer, but if one of you does, by all means post (she knows I am posting this to the blog). By contrast, someone once posted to a readnews group (remember those?)
   Someone out there please help me with this problem: why is {a^n | n prime} not regular? I'm not a student asking for the solution to HW 4, problem 2. Honest I'm not!!
   Looks like a student doing a HW problem.
   
3. ``your blog is my main source for complexity theory'' A scary thought. She needs to get more sources- like Luca and Scott's blog. Or maybe books (remember those?).

SODA papers are out. Plus...

Request: If you want me to post a CALL FOR PAPERS or LIST OF ACCEPTED PAPERS or whatnot for a theory conference or some other conference, please email me and I will almost certainly do it. Not so good to make the request in a comment to another posting since some people do not read the comments (gee, I wonder why :-) ) For those who did not read the comments from yesterdays blog, SODA paper list is out and is here

This raises the questions of which conferences have the most complexity theory in them (say by percent). Here is my rough guess.

1. COMPLEXITY
2. MFCS
3. ICALP
4. FOCS/STOC
5. LICS has an occasional article on descriptive complexity)
6. SODA has an occasional lower bound. The few SODA papers I've been asked to subreferee have all ended up being rejected. The very fact that I am being asked to subreferee is an indicator that they are out of scope.
7. COLT/ALT and the other Learning Theory Conferences.

If I left out your favorite conference, sorry about that.

Search Engines gone wild!

I was curious if my monograph Bounded Queries in Recursion Theory was still available so I went to amazon.com and typed in `William Gasarch'. It had 40 hits. (Move over Stephen King!) I have only written one book, so how is this possible. Here are some of the hits.

1. Bounded Queries in Recursion Theory by Gasarch and Martin. This hit makes sense.
2. Handbook of Discrete and Combinatorial Mathematics edited by I have a 4-page chapter on computability. Does this hit make sense? If I say NO then I have to say say how long a book chapter has to be before it makes sense to have a hit. So I'll say YES.
3. The Complexity Theory Companion by Hemaspaandra and Ogiwara. I was acknowledged in the acknowledgments. Is this hit deserved? NO! (I got quite a few more of these types of hits, some for proceedings where one article acknolwedged me.)
4. An Introduction to Quantum Computing by Pittenger. This book is in the same series as my Bounded Queries books, so the back of the book has a list of all the books in this series. Hence I got a hit. This is nuts!

amazon needs to fix its search engines to be LESS good. ~

Quantum Computing and Quantum Phy.

I have been told quite often that

You don't have to understand Quantum Mechanics to work in Quantum Computing.

Thats a good thing since I've also been told

Nobody really understands Quantum Mechanics.

I've also been told

You don't have to have studied Quantum Mechanics to work in Quantum Computing.

I am skeptical of that. However, I was wondering about the other end- if you do have a background in Physics does it help? So I asked Fred Green (of Green's Conjecture) about this since he has a PhD in Physics, works in a computer science department, and works on Quantum Computing. Here is what he said.

Learning quantum computing helped me understand quantum mechanics better. As a physicist I never thought about measurement theory or entanglement, which were foundational issues, irrelevant to what I was doing. In quantum computing, we reason directly about these things all the time.

He didn't quite answer my question, but he raised a more interesting question. Should quantum physicists learn quantum computing?

In an earlier post I noted that Jerry Seinfeld said Comedians should do lots of proofs. Not for their actual routines, but to better practice their craft. Perhaps its also good advice for people who want to be quantum mechanics (like auto mechanics, but on smaller cars) to learn some Quantum Computing. Not for their actual research, but to better practice their craft.

Social Process and Proofs of Theorems and Programs

How does a theorem get to be believed to be true? There was a paper on this in 1979, Social Processes and Proofs of Theorems and Programs by DeMillo, Lipton, and Perlis. The paper had several points to make:

1. When a theorem in math is proven that is just the start of the process. If it is important enough it will be passed around the community and checked and rechecked. At some point if it survives scrutiny it will be accepted. (Makes you wonder about proofs in the literature that nobody reads- could they be false?)
2. The people working in Program Verification want to give program-correctness the same confidence that we have in Math Theorems.
3. This is not a good idea since Programs cannot be passed around the same way Math Theorem proofs can. (Makes you wonder about the Classification of Finite Simple Groups, or the Four Color Theorem which also cannot be passed around that easily.)

The comments on Program Verification do not really apply anymore since those people seem to have scaled down their claims to building tools to find bugs, and to automatic verification of Protocols written in a SPEC language, which seems far more plausible. (I'm not in the Program Verification Field so if someone wants to tell me I'm wrong, leave an intelligent comment.)

When I first read this article as a young grad students I was very impressed with what it said about math. YES, the proof is just the beginning, but constant checks and rechecks are needed.

The Koblitz Controversy: A reaction

(Guest Blog by Jonathan Katz on the Koblitz Controversy)

Like many others, I was very upset by a recent article by Neal Koblitz that appears in the Notices of the AMS. I'll say at the outset that I actually think the earlier papers by Koblitz (and Menezes) contained some valid points --- I don't agree with their conclusions, and I find their tone objectionable, but I still think they raise some issues worthy of further thought.

What really bugs me, however, is how much publicity Koblitz has managed to get out of this. I see him invited to give talks at many venues, but never see anyone invited to present a counter-argument. (For that matter, I don't see invited speakers at cryptography conferences poking fun at the cryptographic work that mathematicians do.) This does not matter so much when Koblitz speaks at a TCS-venue (any intelligent cryptographer knows that his arguments are overblown), but I think it matters greatly when he speaks in front of an "outside" audience.

For this reason, I thought publication of his article in the Notices of the AMS was inexcusable. Even worse, this latest incarnation of his essay goes beyond being a mere "academic" argument and degenerates to name-calling and belittlement of an entire field and all the people who work in it. (And it seems pretty clear that his feelings extend beyond crypto to CS at large.)

As promised, I have written a letter of complaint to the editors of the Notices. I don't know if it will get published (it is also a bit long), but it is available here (pdf) or here (ps)

P.S. After sending this post to Bill I noticed that Oded also wrote a letter to the Notices of the AMS.

Theory Starts Here! (Informatics Olympiad)

(Guest post by Mihai Patrascu)
A while ago, I promised the community around the International Olympiad in Informatics that I would bring them into the conscience of the theory community, and now I am trying to fulfil this promise. I have written a short " practical guide " of what we, as the theory community, should know and why we should care. Below is your executive summary:

Understand. What happens when you cross homo ludens with scientists? Imagine the Olympic Games, where you throw Computer Science into the arena. In short, you ask each country to send their best 4 high school students, who then compete in solving algorithmic questions.

Appreciate. The problems given in the contest are meant to challenge the brightest young minds in Computer Science. For a quick reference, problems in [CLRS] are "easy". Many questions asked are truly original, and thus can be fun even for a mature audience. Many questions can also make excellent assignments in algorithms courses (with or without a programming component).

Care. Informatics Olympiads are part of our intellectual tradition, and a part that should make us proud. The parallel olympiad in Mathematics is highly regarded in that community. A theory community that embraces the Olympiad is a stronger theory community.

More practically, the Olympiad gives us outreach to the high school level for free. We need a healthy flow of new talent, and the olympiad is already motivating hundreds of the smartest kids to learn theory. Our awareness can tell them that they are on the right path.

Most practically, we should be paying attention to it in the admissions process. The International Mathematics Olympiad, which has been running since 1959, has had a very significant impact on theory.

Our very own Informatics Olympiad is much younger (1989) and the contestant are only now coming of age. However, check out this list for notable theorists coming straight out of the Olympiad. If you want to know how well people are doing on average (and be impressed!), check this out. It is a statistic about the career paths of all Romanians who ever participated in the Olympiad.

RANT about Electronic Refereeing

When you are asked to referee a paper, should you accept the job? That is not todays topic. Today's posting is a rant!
I got a request to referee a paper that I really could not turn down since I'm one of the few people who is qualified This may be reason enough to reject--- if very few people could referee it then perhaps the topic is too obscure. However, obsurity of research is not todays topic. Today's posting is a rant!!
BEGIN RANT
The request to referee was an automatic email. I then had to do the following:

1. Goto a website to accept.
2. Receive an email telling me how to access the paper.
3. Goto another website, click on something to receive another email telling me my password and login.
4. Change my password to one that I could remember. This took a while since they didn't state their rules for passwords, nor did there error messages tell me what the rules were.
5. Goto another website with that password and login and register by giving my name (gee, I think they would already have that), email (ditto), school address, areas of interest, key words of interest (that was really hard- it was a long list and nothing quite fit), my right thumb print, and my left eye retina scan.
6. To get the paper itself the website kept on doing odd things. I called them (by telephone!) and the editor said that I was not being an idiot, the website had problems that day, and they would try to send me the paper, but they were not sure they could access it. I told them that if they did not get me the paper within 24 hours I would not referee it. They got it to me 23 hours 45 minutes later.
7. I am looking forward to seeing if the website will be working when I fill in the referees report, which must be done on the web.

This is insane!
END RANT

I do not think I'm being a luddite to complain about this. Being a luddite (different link) is not the topic of todays post. I do not think that electronic refereeing systems using the web are a bad idea. But electronic refereeing systems are not todays posting. Todays posting was a rant!.

Impact of Facebook platform on CS enrollment

(Guest Blog by Amir Michail) As you may know, the Facebook platform was launched recently amid great excitement. This API allows developers to integrate their web applications with Facebook, a popular social networking service, particularly among students.

So why is the Facebook platform interesting? And what does it have to do with CS enrollment?

Web 2.0 entrepreneurs aim to attract millions of users to their service. The Facebook platform facilitates this by creating a highly viral environment for spreading a web service by leveraging the social network graph. In particular, when a Facebook user uses an application, his/her friends in the social network graph will know about it automatically and they might use it too, thus automatically informing their friends, and so on.

The Facebook platform may very well boost CS enrollment. After all, who cares about an uncertain job market when what you really want to do is to pursue your own startup and make millions?

For more on the Facebook platform and its potential, see this excellent keynote by Facebook's CEO Mark Zuckerberg: excellent keynote by Facebook's CEO Mark Zuckerberg

Now a question for you: as educators, what can you do to take advantage of this phenomenon to increase CS enrollment?

Checkers- Clarification by Schaefer

Aaron Sterling pointed Jon Schafer (the checkers guy!) to my entry and Scott's entry on checkers, and the comments on it. the comments on it. Then Aaron Sterling and Jon Schaefer had an email discussion about the checkers result. Here is the transcript abbreviated.

Sterling: Please clarify what you mean by checkers being solved. As you can see from the discussion, there is lack of agreement on what the Science article really meant.

Schaefer: Checkers has been weakly solved. The game is a proven draw and the proof online gives the sequence of moves for white and black to achieve the draw.

Sterling: More pointedly: what percentage of the total gametree is now determined?

Schaefer: We considered 10¹⁴ positions out of the total search space of 10²⁰.

Sterling: If the search area was pruned, what were the criteria used for that?

Schaefer: Lines of play that were provably irrelevant to determining the final result were ignored.

Sterling: Is there even a shred of possibility that a "supposedly losing" move could in fact lead to a won position, and so certain game lines were improperly excluded from search?

Schaefer: None.

Sterling: Most significantly, perhaps, is this only a statement about 8x8 checkers, or does it generalize in any way?

Schaefer: 8x8 checkers only. The program can, however, be used to solve any game of checkers (it does, in fact, work for an 8x8 variant and 10x10 international checkers).

FOCS registration Open

(Guest Informational Post by Phil Klein)

Registration has opened for FOCS 2007, which will take place in Providence on October 20-23.  Please go to

http://focs2007.org

Note that the early registration deadline is September 20, and the deadline for reserving a room at the hotel at the conference rate is also September 20.  (The hotel's regular rate is much higher.)

The Knuth Prize lecture will be given by Nancy Lynch on October 21.
A program of tutorials takes place on October 20, the Saturday before the regular conference program begins.  The tutorial talks are as follows:

Terrence Tao
Combinatorial Number Theory

Dan Boneh
Recent Developments in Cryptography

Daniel Spielman
Theory and Applications of Graph Spectra

Abstracts for the tutorials should be available soon.

A New Job and Journal

Guest Post by Lance Fortnow

As an anonymous commentor mentioned on Monday, I am moving to Northwestern University EECS in January. Northwestern also hired Jason Hartline and Nicole Immorlica so I have an exciting opportunity to join an up and coming theory group without having to move my family.

In other news the ACM Transactions on Computation Theory has been approved and will be starting up soon with yours truly as editor-in-chief. Watch for details and get your papers ready.

Graduate Complexity Theory Course

I will be teaching a Basic Graduate Course in Complexity Theory in the fall. Complexity Theory has too many theorems that you absolutely must cover. Hence you have to pick and choose. The people taking my course will largely not be doing theory. Hence I want them to come away knowing some very definite things. Also, I want every part of the course to have a definite goal they can appreciate. Here is the rough syllabus.

1. Defining TM's, Time-Hierarchy Theorem. NL=coNL. Savitch's theorem.
2. Cooks Theorem, some NPC reductions. Mahaney's theorem, PH, Karp-Lipton theorem.
3. If GI is NPC then PH collapses. (This will use PH, Karp-Lipton. Will also need hash functions, AM protocol for GIbar.)
4. If PARITYSAT is in P then SAT is in R. (This will use some of the machiney devoloped for GI.)
5. Everything in PH is \le_T^p #SAT. (Toda's theorem.)
6. If CLIQUE can be approximated then P=NP. (STATE PCP, give proof of some easier cases, but do not proof the full theorem or even try.)

Other topics that would be reasonable to cover: Baker-Gill-Solovay Oracle, Hard vs Random stuff, PARITY not in constant depth, and CLIQUE not in Monotone P. Not doing BGS-oracle since I'm not doing enough proofs that relativize in the first place. Not doing Hard vs Random since its a bit hard and a bit random for this level of course. Not doing Circuit Stuff since that does not fit in that well with these topics (concrete vs. abstract complexity). Any of these points are debatable.

I'll be giving out my own notes. My experience is that using other peoples notes does not work, and others using mine does not work. My notes work for students taking my course, who see my lectures, and who have access to me. But they would not be good for anybody else.