Is Math too hard?

Are humans good at Math?

In the movie Oh God Book II God (played by George Burns) says that Math was a mistake, I made it too hard!. While I am reluctant to contradict God, George Burns, or God as portrayed by George Burns, scientists have found evidence that people are pretty good at math. At least people have known about numbers for a far longer time than previously thought. See this article. What does this mean for us? The next time one of your students says I can't do this! I'm just not that good at math! you can tell them that this is just not true.

An Aside: Before posting this I wanted to verify that that quote really was in that movie. I would have thought it would be a quote that math people, or people who think math is hard, or math people who know math is hard, would remember. When I googled it all I could find was a comment on this blog entry of Scott's by Bill Gasarch. Not what I would call a confirmation. It may be that my quote is not quite exact. If anyone knows for sure (e.g., has the DVD and checks it) let me know.

Doing it OLD SCHOOL!

If you browse the Univ of MD Schedule Web pages for the last few years I would:

1. Ask you why you were doing that. Seems like an odd use of your time.
2. Point out to you that Automata Theory which usually gets around 8 people got 23 (it competes with crypto as noted a few blog entries ago).

Why the uptick? Did we use email? blogs? a websites? twitter? FACEBOOK? eBay? None of the above. We had tried some of those in the past to NO effect. We did it Old School! I went around to the classes that feed into Automata Theory and TALKED about them for 5 minutes each around registration time. And the talks were off-the-cuff. No PowerPoint, no fireworks, no technicolor show with an intermission. Also we told advisers to be on the lookout for people who might want to take it and tell them while advising.

1. I had a prior post on why email is less effective then is used to be (I can't find the post- if you know where it is let me know.) To summarize from memory- people get too much email and some goes to SPAM filters or can be claimed to have.
2. (A colleague of mine suggested this.) If I just EMAIL about a class, I have not spend much effort and the students sense that. If I go out of my way to talk about the class then the students think that I care.
3. There are some other explanations for some of the uptick: Comp Sci enrollment is up (might account for 4 students) and by a fluke we have 2 grad students taking the course (which accounts for 2 students). But going from 12 in Spring 2009 to 24 in Spring 2010 is alot. (It was taught be people who are thought us as good teachers both times.)

The point is, if you want something to get attention locally do it old-school! Or at least do it old-school in conjunction with high-tech.

What is in MY automata theory course/What should be

In the last post I pondered what was more important: Automata Theory or Crypto. This raises the question of what should be in a course in automata theory. Rather than discuss that I will tell you what is in mine and see what you think. (ADDED LATER: YOUR COMMENTS HAVE MADE ME RETHING THINGS. I WILL ADD MINMIZING DFA'S TO THE COURSE THIS SEMESTER. I AM JUST FINISHING UP REG STUFF SO I CAN DO IT NOW.)

The standard topics are:

1. Regular Languages: DFA's, NFA's, Reg Expressions.
2. PDA's, CFL's.
3. Turing Machines, computable and c.e. sets.
4. NPC

The following make this course a bit different than others, though not much. All the thing listed below that I claim I WON"T do are definite- I WON"T do them. All the things that I claim I WILL do are less definite I can't do all of them. I'll see how it goes and which ones I will do.

1. Decidability of Weak Second Order with S and ≤. The language has quantifiers that range over finite sets, quantifiers that range over natural numbers, and symbols for Successor and ≤. The proof uses Reg Languages. We do it in the Reg Language section and then revisit it when we do decidability. At that point I will also tell them (but not prove) about some theories that are undecidable. We also do decidability of Presburger arithmetic (quantify over naturals, have + and ≤) which follows from decidability of WS1S easily. Will also talk about decidability of S1S and omega-automta, but not prove anything. This did not take up too much time because I presented alot of it as more examples of regular languages. This material is not in any textbook that I know of, however see pages 8-28 of this PhD thesis.
2. I am NOT going to do the algorithm for MINIMIZING a DFA.
3. I am NOT going to do Context-Sensitive Languages.
4. I am NOT going to have them prove things that are obvious, like that S-->aSb, S-->emptystring generates {aⁿbⁿ}. Generally I am against having students prove things that are obvious.
5. I am NOT going to have them ever program a Turing Machine. I will tell them they can do everything and rarely refer to them ever again. I DO need the definition so that I can prove Cook's theorem.
6. I am NOT going to to Primitive Recursive functions.
7. In the NPC section I WILL DO the protocol for, in our language, NGI (non-Graph-Isom) is in AM.
8. In the NPC section I WILL DO the protocol for, in our language, given bit-commit, 3-COL is in ZK. (I may to other ZK protocols as well.)
9. In the NPC section will do that Vertex Cover with FIXED k is in O(n²) (I know that better is known.) Why? Because this is a very good example of an obvious thing (can't do better than roughly O(n^k)) being WRONG. Shows the NEED to prove things.
10. Might do NSPACE(n) closed under Complementation. Might not- this may be conventionally difficult for this audience. And we really wont' be talking about space anyway.
11. Let SUBSEQ(L) be the set of a subsequence of L. I will, throughout the year, do the following: Show that if L is regular than SUBSEQ(L) is regular, Show that if L is context free than SUBSEQ(L) is context free, Show that if L is c.e. than SUBSEQ(L) is c.e. All of this leads to material I discussed in this old post. I WILL NOT prove that if L is ANY language then SUBSEQ(L) is regular, but I may talk about it.

What is more importantt: Automata Theory or Crypto?

The way the requirements are set up at Univ of MD at College Park, without getting into details, has set up a competition between Crypto and Automata Theory That is, a student might take one or the other, but taking both does not serve her well for the requirements. Hence the students get to decide which one is more important, Crypto or Automata Theory. We did not plan it this way, it just happened. Automata Theory is Reg Languages, CFG/PDA, Computability theory, NPC. (A later post will expand on this since I am teaching it this semester.)

1. The students overwhelmingly take crypto. One year 150 students took Crypto (one section of 50 in the fall, two sections of 50 each in the spring) and 8 students took automata theory. Both courses are always taught by people who are regarded as good teachers, so that is not the issues.
2. I tend to think that Automata Theory is more important, but I may be biased. I also think that Automata Theory can be understood pretty well, whereas to understand crypto you really need to understand some Number Theory and even some security. Hence it is a strange stand-alone course.
3. Some students think that the crypto course will get them a job. A course in security may get them a job, but just crypto I kind of doubt.
4. Since more students choose Crypto we offer it more often. Since we offer it more often more students take it. (I exaggerate the circularity.) Also, its cross listed with Math so some math majors take it. This may account for some of the difference but not even close to all of it.
5. So, how does your school do this? In particular, do you let the students tell you what course is more important, or do you tell them? Is it bad if they tell us? YES if we end up with courses on twitter, NO if the students are more aware of what is important then we old academics are.

A problem about Graph Partitions (guest post)

(Guest post from Richard Taylor who requests information on a problem.)

The following graph partition problem arises in connection with studies I am doing on a particular dynamical systems problem. I wonder if there are any complexity results on it. Given a 3-regular graph, can the vertex set be partitioned into 2 sets in such a way that the induced subgraphs formed each have vertices of degree at least 2? Could this be NP complete? There are a few results on vertex partitions I have found in the literature - but none quite like this.

First Request from Bill G: In the past I have posted on problems and have had comments tell me that its well known or falls out easily from some theory, but then not give me a reference or proof sketch. Please, if you are going to say its known, give a reference or proof sketch.

Kurt Mehlhorn to receive EATCS award

Kurt Mehlhorn will receive EATCS award! Read about it here.

He has had a LONG and PRODUCTIVE career with many EXCELLENT papers. While he is mostly known for data structures and algorithms and Comp Geom, he did do some complexity theory early on. Here is a list of his papers up to 2007. Note that the first few are in complexity theory.

People in TCS can change fields easier than math since there is less background to learn. At least that was true at one time. I think it is harder to switch fields in Comp Sci now then it was then since now we know more.

e to the pi vs pi to the e

(ANSWER to Trivia Questions from Last Post: The last president who became president NOT by being VP and having the prez die, but then did not run again, was Rutherford B. Hayes. Hayes and Obama are the only presidents who have law degrees from Harvard. For more on both of these questions see this excerpt from my Prez Trivia Quiz.)

When I was 12 my school got a very primitive computer. The teacher asked me what I wanted it to do for me. I said

I want to know whats bigger e^π or π^e.

I typed both of them in, but I forgot the order I typed them in so I didn't find out. I didn't try again because I realized that even if I found out the answer it would not tell me a reason for the answer.

I had forgotten all about it until last week when I got a review of the book When Least is Best (book by Paul Nahim, review by Yannis Haralambous) in my capacity of SIGACT NEWS book review editor. Here is a quote from the review:

Imagine you are stranded on a desert island (without logarithm tables or computers) and--- probably due to an emotional shock---your only concern is to find out which one among numbers π^e and e^π is bigger. The solution is: take h(x)=ln(x)/x, take the derivative twice to prove that x=e is a maximum, and that gives e^π is bigger.

I am sure this is well known; however, since I didn't know it until last week I hope this will enlighten some of my readers.

Prediction on Presidents Day

Its PRESIDENT"S DAY so I have two predictions: One about the election of 2012 and one about P vs NP.

ON P VS NP: I have one prediction about P vs NP. It is not about when it will be solved (though I think this will be a long time). Look at the separation NC¹ ≠ AC₀. This was NOT achieved by taking a problem complete for NC¹ (the word problem for S₅) and showing it is not in AC₀. Instead a different problem in NC¹, PARITY, was shown to not be in AC₀ (CHECK- is it known that PARITY is NOT complete for NC¹? I think so - PARITY can be done in width 2 , poly sized BP and NC is equivlaent to width 5 poly sized, is probably the main part of the proof.)

I predict that P ≠ NP will be proven by showing some problem that is in NP but NOT NPC is not in P. The NPC problems seem to be hard to prove things about. Hence a problem in NP but not NPC may be better. Factoring is a candidate for this. Graph Isom may also be a candidate--- its like PARITY in that its very delicate. But it may very well be in P.

ON THE ELECTION OF 2012. For the Prez election of 2008 I predicted, before the primaries, that the candidates would be Barak Obama and John McCain, and that Barak Obama would win. I never blogged about it so my readers may be skeptical that I made such a prediction. Hence I will, today, predict the nominess for 2012: Barack Obama and Mitt Romney.

Barack Obama is obvious- TRIVIA- The last president to decline to run for a second term was LBJ. Note that he originally got to be Prez because he was VP when JFK died. The one before that was Harry Truman. Note that he originally got to be Prez because he was VP when FDR died. Who was the last president who obtained office NOT be being VP when the Prez died, who did not run for a second term? MORE TRIVIA:Call this prez X. Give a non-trivial trivia question for which the answer is Barack Obama and X. (I will answer these at the beginning of my next post.)

Mitt Romney- The republicans tend to give the nomination to someone familiar to them. Like the guy who came in second last time. Palin is also familiar to them, and she may run in the primaries, but I do not think she will get the nomination.

I also predict that Obama will win.

FOCS 2010 CALL FOR PAPERS is out!

(Univ of MD at College Park had Monday, Tuesday, Wed, Thursday all off. I've spend most of that time shoveling snow, so I am tired. Hence I am glad to have a SHORT post today- easier on the hands and arms.)

ADDED LATER-- I won't post Friday - instead I will add to this post. Note that there is NO PAGE LIMIT for FOCS submission! Is this a new policy? Have other conferences done this? It makes sense with e-proceedings to have no page limit for FINAL versions, but for Submissions. Might be hard on the committee and the sub-referees. PRO- people can include complete proofs and may be expected to. This will lead to better quality submission and less chance of error. CON- if you are restricted to 10 pages you are forced to make your point and shut up. PRO- Your submission and your final version and your journal version can be similar so less hassle changing formats. What do you think?

FOCS 2010 call for papers is out. Where is the link? You just read it! I did? Third Base!

Most important byte of info: April 7 is submission deadline. If a student said that he was sick and had a doctors note, you would likely give him an extension for a deadline. For FOCS, if a potential submitter tells the program chair that he is sick, I doubt he'll get an extension.

IF you had your paper rejected from STOC then should you submit to FOCS? It would be nice (though hard to really do) if the reports from STOC said Even though the paper was turned down, it was one of those papers which could have gone either way, so it could get into FOCS or XXX. or Your paper is not worthy of STOC or FOCS or XXX.

I am writing THIS before I actually post (duh). Right now if you type FOCS 2010 into Google, Our FOCS conference is the SECOND entry. Here is hoping that this post will boost it to the top.

STOC and More

The Snows of Maryland are keeping Bill away from this blog again. Here in Chicago we deal with snow (and even earthquakes) in stride--my kids still have yet to have a snow day this year.

So I'm back for a day to bring you some news.

The STOC accepted papers list is up, Shiva Kintali is collecting PDF pointers and Noam Nisan pulls out the AGT papers. Lots of goodies this year. You can change base without losing space (love that rhyming title), save space with algebrization and adding quantum to interactive proofs keeps it in PSPACE. 

You just don't see a lot of BLANK is computable results in STOC these days so nice to see a paper with BLANK=HOM=Is a given homomorphism of a regular language expressed by a tree automata itself regular? Sound technical but it actually has connections to XML.

So come to the conference. As Bill mentioned earlier, there are travel awards available for needy students even if you don't have a paper. Apply for visas if needed as soon as possible (click here if you need a letter). The Complexity and EC conferences will both be held also in Cambridge immediately following STOC.

The other big news, according to the Center for Computational Intractability, theory's own Subhash Khot wins the 2010 NSF Waterman award. The NSF gives away only one of these awards each year to a young researcher across all of science.

We are entering CS award season so keep an eye out for the Knuth Prize (the Knuth Prize Lecture will be at STOC), the EATCS award and Gödel Prize (presented at ICALP), Turing and other ACM awards. The SIGACT Distinguished Service award nominations are still open until March 1st which will also be presented at STOC.

What is an Elementary Proof?

What is an Elementary Proof? Different things in different contexts.

1. An Elementary Proof is one that does not use Complex Analysis. Basic Calculus is fine. This was the criteria when people asked for an Elementary Proof of The Prime Number Theorem. Such a proof was found by Erdos and Selberg. (See this paper for the history) Later Oliver Sudac (TCS, The Prime Number Theorem is PRA Provable, Vol 257, NOT Online) showed there is a proof in Primitive Recursive Arithmetic which is weaker than Peano Arithmetic. An interesting article on this which IS online is by Jeremy Avigad on all of this is at Number Theory and Elementary Arithmetic. From what I hear, the original proof is still the easiest way to prove it. (NOTE- Oliver Sudac, if you are reading this put your paper on line. If you do not then over time it will be called ``Avigad's theorem''.)
2. An Elementary proof is one that can be taught to a class of bright college students in about two hours. If you hear someone say Shelah's primitive recursive bounds on the VDW bounds is elementary this is what they mean. (See here. for the paper.) )
3. An Elementary proof is one that does not use advanced techniques. The original proof of Szemeredi's Theorem is rather difficult; however, it does not use advanced techniques. You could probably teach it to a class of bright college students in about two months. Even so, I would hesitate to call it elementary. It might be easier to learn the background mathematics for one of the non-elementary proofs rather than follow the elementary one.
4. An Elementary proof is one that some bright high school students can come up with during a High School Math Competition.
   1. The following is elementary: Show that any for any 3-coloring of the natural numbers there exists x,y that are the same color such that x-y is a square.
   2. The following is probably not elementary: Show that any for any 4-coloring of the natural numbers there exists x,y that are the same color such that x-y is a square. I wanted to put it on the Maryland Math Competition to find out if it was elementary, but alas they didn't let me. I do not know of a proof that a bright college student could do on his own. The theorem is true by poly VDW thm; however, I would very much want to see an easier proof.
   3. The following is elementary: Show that if n is a power of 2 then if there are 2n-1 integers then some n of them sum to 0 mod n.
   4. The following is probably not elementary: Show that if n is any integer then if there are 2n-1 integers then some n of them sum to 0 mod n. The proof in here is elementary in that you could explain it to a bright college student in 30 minutes; however, I don't think they could come up with it themselves.
   5. In Elementary Particle Theory it is the particles that are elementary, not the theory.

It is hard to pin down Elementary rigorously. I just want to be able to understand a proof and the intuition behind it. But we can't define elementary in terms of what I want.

What theorem would you most want to see an elementary proof of? For me it would be Gowers bounds on the VDW numbers.

The more things change the more things change

There have been some articles on how much things have changed because of technology. One from the Washington Post Magazine, titled Going, Going, ..., Gone lists out items that are fading out of our lives Here are a few:

1. Cash: When is the last time you used cash in a transaction that was over 20 dollars? Over 10?
2. Slide rules: I thought they were already gone gone gone. You can buy them off the web here. The site does not seem to think of them as antiques.
3. Truly blind dates: In my day we couldn't Google our dates ahead of time.
4. FAX machines: Not sure they are really going going gone. If they had come out earlier they would be far more popular. If they had come out later they would have been far less popular. Are they here to stay?
5. Secretaries: I can't imagine having someone type my papers for me or book a trip for me.
6. Tonsillectomies: I actually got one when I was 8. I hope that wasn't a mistake.

However, nothing demonstrates how things have changed better than this unaired Pilot of the TV show 24 from 1994 here. ~

Time Space Tradeoffs for SAT- good resuls but...

This is a real conversation between BILL and STUDENT (a Software Engineering Masters Student who knows some theory). As such there are likely BETTER arguments BILL or STUDENT could give for there point of view. I invite you to post such as comments. (ADDED LATER: Some of the comments below DO give VERY GOOD arguments for why the results are interesting. I URGE anyone reading this now to read the comments. They are an integral part of this post, more than usual.)

BILL: In 2007 the best student paper award at COMPLEXITY went to Ryan Williams for proving that SAT cannot be done in time O(n^1.801...) and O(n^o(1)) space!! The constant 1.801 is actually 2cos(π/7). (The paper is Time Space Tradeoffs for Counting SAT mod P. Note that the space is n to the little-o(1) which would include log space.)

STUDENT: Doesn't everyone think SAT is not in P?

BILL: YES.

STUDENT: So what's the big deal in proving that SAT is not in time O(n^1.801...) and not much space?

BILL: Its a stepping stone towards better lower bounds!

STUDENT: Are better lower bounds using these techniques likely?

BILL: Well, it is thought that these techniques cannot possibly get beyond SAT not in O(n²).

STUDENT: So... why is it such a good result?

BILL: Actually he proved more than that. He proved that, for all but one prime p, finding the number of satisfying assignments mod p requires O(n^1.801) time if you insist on O(n^o(1)) space.

STUDENT: Is the number of satisfying assignments mod p problem a problem people care about?

BILL: Complexity Theorists care about it!

STUDENT: I meant real people!

BILL: Um, ur...

STUDENT: Are there any interesting upper bounds on the number of satisfying assignments mod p problem so that the lower bounds are a counterpoint to them?

BILL: YES! There are some poly upper bounds are known for planar read-twice monotone formulas mod 7.! (see this paper by Valiant.)

STUDENT: Do people care about the number of solutions of planar read-twice monotone formulas mod 7?

BILL: Complexity Theorists care about it!

STUDENT: I mean real people! Oh. Are we entering an infinite loop?

BILL: The planar read-twice-monotone-formulas-mod-7 result is an example of a very powerful framework for algorithms.

STUDENT: So that paper may be important, but why is the SAT time-space tradeoff paper important?

I like these results, but STUDENT raises a good question: Are Time Space Tradeoffs for SAT important? IS SAT mod p important? I would argue YES since they are absolute lower bounds and there techniques combined with something else may yield more interesting results. However, if you have better arguments please leave comments.

Should Time Space Tradeoffs for SAT be taught in a grad theory course? There is one in Arora-Barak that is not hard. Hence it likely will be taught. If you teach it I hope you have students challenge you as STUDENT challenged me. It will mean they are awake and care. However, be prepared to answer them.

When this was taught in seminar recently the question arose: In the paper Time space Lower bounds for Satisfiability by Fortnow, Lipton, van Melkebeek, Viglas showed the following: For all c < φ (the golden ratio) there exists d such that SAT cannot be solved in time O(n^c) and space O(n^d). The techniques are such that it could have been proven in the 1970's. So why wasn't it? The seminar speculates that back then people were not so pessimistic about lower bounds to consider this a problem worth looking at. Now people do.

Naming and Ranking

Martin Kruskal invented Soliton Waves which were a very important concept in Physics. (NOTE- one of the comments clarifies this statement.)

Rebecca Kruskal (Martin's Granddaughter): Daddy, how come they are not called Kruskal Waves?

Clyde Kruskal (Martin's Son, Rebecca's Father): You can't name things after yourself.

Rebecca Kruskal: Why not?

Rebecca raises a good question. In academia the etiquette has evolved that you simply do not name things after yourself. Why is this? Is it a good thing? How did this tradition get started? Have people tried to name things after themselves? What happens in other endeavors?

On a related topic: if you are asked to give a list of the top items in your field then is it okay to list some of your own?

In THE NEW BOOK OF LISTS by Wallechinsky (spell check wanted me to change the name to Lewinsky) and Wallace they have several lists where an expert in X lists his favorite things in X. Some include their own work:

1. Johnny Cash's 10 Favorite Country Songs of all Time includes his own I Walk the Line (at number 1) and Folsom Prison Blues (at number 4). To be fair, they are awesome songs!
2. Oliver Stone's 12 Best Political Films of all Time actually lists 10 movies (films?) but then says Stone Notes: And two more with apologies: 11-12. JFK and Salvador. Because I never thought either could be made, much less be appreciated by a large audience. This strikes me as a good way of doing it- since 10 is the usual number on a list make it 12 and include two of your own and apologize for it. However, the movie JFK was way too long. The point of the movie was made more concisely here
3. Federico Fellini's 10 All Time Favorite Films include his own 8 1/2 as number 10.
4. Lucille Ball's 10 Favorite TV Series has as item 10 and of course I Love Lucy.
5. Charles M. Schultz's 10 Greatest Cartoon Characters includes, at number 1, Charlies Brown and Snoopy.

If I was asked for my favorite theorems and I had one that I thought was reasonable I wouldn't put it on the list. But I would add at the end something like With apologies I include ..... I think it is unfair to compare your own work with others.

Travel Support for Grad Students who GOTO STOC 2010

If you are a grad student and want to goto STOC 2010 there is travel support money that you can apply for. See here for details.

What is the best way to get this information out? What is the best wayy to get any kind of information out?

1. Websites. For STOC there is an obvious website, and indeed it is there under Travel Support. This works for conferences. It does not work if the info is hidden deep in a non-obvious place OR if its not there and should be. This happens more than it should. Big Plus: Posting on a website is NOT intrusive like email.
2. Blogs: There are so many blogs and its not clear who reads which ones. Also, some do not do annoucements like this. However, blogs are not intrusive and some people who did not know the info now do.
3. Email: We all get too much and ignore lots of it. Not reliable. See this blog entry for more on that.
4. Twitter: There are still people who don't get tweets. I am one of them. Though I do read Lance's Tweets on the Complexity Home Page---to see how he tweets my posts.
5. Facebook: There are still people who don't do facebook. I am one of them. I may have to at some point. See here.