Computational Complexity

Monday, December 31, 2007

 
Presidential Math

Posted by Lance

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.

6:40 AM #

Thursday, December 27, 2007

 
Oral Homework

Posted by Lance

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.

6:02 AM #

Monday, December 24, 2007

 
The Twelve Days of Tenure

Posted by Lance

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.

6:01 AM #

Friday, December 21, 2007

 
A Bad Deal

Posted by Lance

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.

2:06 PM #

Wednesday, December 19, 2007

 
More on VDW over the Reals

Posted by Lance

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.

7:09 AM #

Monday, December 17, 2007

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

Posted by GASARCH

Bad news for American Science Funding: click here

Good news for Australian Science Funding: click here

10:32 AM #

Friday, December 14, 2007

 
Complexity Theory Class Drinking Game

Posted by GASARCH

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.

4:58 PM #

Monday, December 10, 2007

 
An ill define question inspired by that HS question

Posted by GASARCH

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

12:53 PM #

Friday, December 07, 2007

 
Funny Answers on a Math Olympiad (MD)

Posted by GASARCH

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.

1:56 PM #

Wednesday, December 05, 2007

 
Crypto problem inspired by politness

Posted by GASARCH

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.

12:47 PM #

Archives