Friday, February 27, 2009

Conventional Wisdom

Richard Lipton has a relatively new weblog. Quite a few provocative posts, particularly on the following theme.
Hopefully, these posts will raise issues about conventional wisdom, and these issues will cause you to re-examine whether or not “obviously” P≠NP. 
Lipton even suggests we should have a stimulus package for P = NP.
I would like to suggest that the government (NSF?) should fund a major project on P=NP, with the goal of accelerating the discovery of a solution. 
I agree with Lipton on the importance of the P v. NP problem, but I am a strong believer of the conventional wisdom. Just because many people believe in something that doesn't mean you should doubt it.

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

Thursday, February 26, 2009

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

I have received the following legit email several times (paraphrased):
`Hi, I am NAME (A NAME I DO recognize from my past). Are you the same Bill Gasarch who when TRUE FACT ABOUT ME (e.g., `Went to John Dewey High School in the late 70's')
This often resuls in a short email conversation along the lines of What are you doing now?

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

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

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

Wednesday, February 25, 2009

Proof-Ready Projects

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

Yesterday's Science Times has two articles on the Obama administration and science. John Tierney writes about how scientists do not always frame science policy issues well. Gardiner Harris and Kenneth Chang write about the immediate needs for the science money in the stimulus bill.
"It would be the height of embarrassment," Acting NIH Director Raynard Kington said, "if we give these grants and find out that institutions are not spending them to hire people and make purchases and advance the science the way they’re designed to do."
No problem says Harris and Chang, universities have plenty of "beaker-ready" projects ready to go.

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

Tuesday, February 24, 2009

The FOCS Call


"Optimization" is added to the list of topics.




This one puzzled me so I asked Dan about it.
It will have a few uses:
So the Call asks for both details and essence. Interesting.

Monday, February 23, 2009

Seeking the NON-Elementary proof of...

Consider the following:
Canonical VDW thm: For any k &isin N, for any coloring of N with an infinite number of colors, either
  1. there exists an arithmetic progression of length k where all of the elements are the SAME color, or (e.g, if k=5, 10 RED, 14 RED, 18 RED, 22 RED, 26 RED).
  2. there exists an arithmetic progression of length k where all of the elements are different colors (e.g, if k=5, 10 RED, 14 BLUE, 18 GREEN, 22 YELLOW, 26 PURPLE).
Henceforth I will refer to this as CVDW.

Szemeredi's Thm: Let k &isin N. If A &sube N has positive upper density (liminfn &rarr &infin |A &cap {1,...,n}|/n > 0) then A has an arithmetic sequence of length k.
(Henceforth SZ) I have seen the following statement in two papers and one book (I'll paraphrase.)
It is easy to see that SZ implies CVDW.
  1. I was unable to prove this. If someone out there can supply the easy proof please do so in the comments (my curiosity is far bigger than my ego).
  2. The first step of the proof is obvious: if some color has positive density then we are done. So assume that they all have 0 density. The seconds step MIGHT be to take the set
    { x | COL(x) ¬in {COL(1),...,COL(x-1)}
    and show that it has positive density. But I don't know how to prove that, or if its even true.
  3. If I assume that each color appears finitely often then I can prove there is a colorful k-AP using VDW thm. (I leave this to the reader.)
  4. There is an elementary proof by Promel and Rodl. (An elementary proof of the canonizing version of Gallai-Witt's thm, Journal of Combinatorial Theory A, Volume 42, Pages 144-149, 1986. I have not been able to find it online, so if someone knows an online version let me know.) They actually show (as the title indicates) an elementary proof of the Canonical Gallai-Witt thm (multidim VDW), which I won't go into here. I have written up just the elementary proof of CVDW here: writeup.
LATE EDIT (Feb 26, 2009): One of my readers send me an ONLINE version of the paper. It is now at originalpaper.

Friday, February 20, 2009

The New Facebook Generation

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

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

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

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

Thursday, February 19, 2009

Movie Mistakes- or are they?

Note the following two movies mistakes. Or are they mistakes?
  1. In The Wizard of Oz when the Scarecrow gets his diploma (instead of a brain) he says the following:
    This is incorrect. I suspect my readers spotted this mistake while watching the movie. If you type
    "Wizard of Oz" isosceles
    into google you get over 2500 hits-- far less than I would have thought. (Though if you replace isosceles with pythagorean you get over 8000 hits.) So this error is somewhat known. But is it an error? Possibilities:
    1. The writers and everyone who proofread the script did not catch this. Realize that this is not hard math. Wouldn't someone have noticed it?
    2. One of the points of the movie is that the Scarecrow is already smart. Hence the writers are trying to show that he was smart (though didn't know math) both before and after getting the diploma, so the diploma didn't change anything except his confidence. And when it comes to math, a misplaced confidence.
    3. Recall that the movie is all Dorothy's dream. The writers were making the point that Dorothy didn't know the proper way to state the theorem.
  2. In Miracle on 34th street (1947 version) Kris Kringle, who claims to be Santa Claus, states that he has passed psychological tests, and brags that he knows that
    John Quincy Adams' vice president was Daniel Tompkins.
    But this is incorrect! John Quincy Adams's VP was John Calhoun! (Tompkins was James Monroe's VP.) How well known is this error? If you type
    "Miracle on 34th street" Tompkins
    into google you get over 1000 hits (far more than I would have thought). Is this really an error?
    1. Daniel Tompkins was our 6th VP. John Quincy Adams was our 6th Prez. They just didn't line up (see chart at the end of the answers to my prez quiz). Hence it was an honest mistake on the part of the writers (I find this far more believable than the Scarecrow-math error not being detected.)
    2. The writers were trying to tell us that Kris Kringle wasn't Santa Claus. Or at least put some doubt in our minds. Of course, that would only work if the audience knew their vice presidents. (Easy now with the excellent book Bland Ambition: From Adams to Quayle-- The Cranks, Criminals, Tax Cheats, and Golfers who made it to Vice President but harder in 1947 when the movie was made.
    3. There have been two remakes of the movie (that I know of) but I don't know if they contain the error. If you know, let me know.

Wednesday, February 18, 2009

A Great way to use a math blog

  5. Clearly I wish them well.

Tuesday, February 17, 2009

Sloan Fellows

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

Monday, February 16, 2009

The Office

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

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

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

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

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

Friday, February 13, 2009

STOC Papers

Last reminder: Complexity submission deadline tonight midnight Eastern.



Thursday, February 12, 2009

Baseball Families and Math Families

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

Bill James, the baseball statistician, once had an article on measuring Baseball Families. Who was the best baseball family? Would it be ...
  1. The Alous: Felipe, Jesus, Matty were brothers. Moses was Felipe's son. All made the major leagues, and some of them were pretty good.
  2. The Bonds: Bobby and Barry Bonds. Father/Son- both excellent. While you might rather have them then the four Alou's on your team, having four in a family just seems like a stronger family.
  3. The Aarons: Hank and Tommie Aaron. Hank was a great player who hit 755 home runs (without steroids). Tommie, his brother, had a very short career. Even though its a real family, still doesn't seem like the right answer.
  4. Babe Ruth alone: Bill James him rates as the best player of all time. Hence the "Ruth family" would seem to be a very good baseball family.
So, how to go about the question of who is the best baseball family ever? First we need a way to assign to a player some number saying how good he is. Bill James has already done this via a method called win shares. The idea is that you assign to a player how much he helped the team win. This is very complicated and I won't explain it here. However I will point out that it can't be negative and it varies quite a bit. For example Hank Aaron had 643 win shares, while his brother Tommie had 15. For some examples of players with high win shares see this.
So, you could just take the sum of the family members win shares. But this makes the family of one, the winner. We want a real family to get some credit for being a real family. Bill James' solution: Say the best person has a1 win shares, the second a2, etc. a1 > a2 > ... > an. Rate the family via a1 + 2a2 + ... + nan. Under this metric the Alou brothers were the best baseball family as of 2003. See here for the numbers.

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

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

Who are the best Math families of all time? Here are some, not in order. I am sure there are more. Corrections and additions welcome! (I may make a website out of it.) I only count a family if it has at least three members and all of the people are related by blood (sorry Blums). Aside from that, I am fairly informal. This list is not meant to be the final word.
  1. The Bernoulli Bunch Link. There were eight of them. Jakob-Bernoulli numbers, Nickolaus-Prob theory and Geometry (NOT Bernoulli Dist), Johann- Brachistochrone problem and possibly L'Hopital's rule, Daniel-Bernoulli's principal (also physics and probability), Wikipedia does not have info on the other four, but says they were math folks.
  2. The Kruskal Kin: William (Kruskal-Wallace test in statistics), Martin (Solitons), and Joseph (Min Spanning tree, Kruskal Tree Theorem (set of all trees under embedding is a well quasi order), Kruskal-Katona Theorem). They are all brothers. Martin's son is Clyde (Parallel Computation, Coloring the Plane). Clyde's son is Justin (Ramsey Theory, though he's still in High School, so perhaps shouldn't count). William's son is Vincent (Computer Science-IBM research). Rosaly and Molly Kruskal are sisters of Martin/William/Joseph. They do not do math, but Molly has two sons who do math: William Kahn (statistician), and Ted Kahn (Statistical Software); and Rosalie's son is Jeremy Evnine (OR, Math Finance). (Using Clyde's theory these people would count some.) The following does not count as he is not a blood relative: Joe Kruskal's son-in-law is Neal Madras (Math prof at York Univ in Canada).
  3. A Nest of Noethers: Father: Max Noether one of the finest mathematicians of the nineteenth century according to Auguste Dick who wrote a book on Emmy Noether. Max's son was Fritz Noether. Fritz Noether. Max's daughter was Emmy Noether the most important woman in the history of mathematics according to Einstein and others. (That was meant as a compliment but sounds so odd nowadays.) A great mathematician independent of her gender. The only father-son-daughter combination that I know of.
  4. The Markov Chain: Andrey Markov (Markov Chains), his brother Vladmir Markov (Markov's inequality co-authored with his brother), and Andrey Markov Jr. (logic) son of Andrey Markov.
  5. The Browder Brothers: Felix (PDE's), William (Topology and Geometry), and Andrew Browder (Analysis).
  6. A Litter of Lenstras: Hendrik (Computational Number Theory), Arjen (Crypto), and Jan Karel.
Interesting misses:
  1. A Research of Rabin's: Michael and Tal. A Father-Daughter both in Crypto. Probably the only such.
  2. A Manifold of Millars: Terry and Jessica. A Father-Daughter both in Recursive Model Theory. Definitely the only such.
  3. A Troop of Tardos': Eva and Gabor. The only other Brother-Sister combo I know of is the Noethers.
  4. The Courant Clan: Richard Courant (Math), Hans Courant (son of Richard, Physics), Ernst Courant (son of Richard, Physics) Ted Courant (son of Hans, Math), Jurgen Moser (son-in-law of Richard, Math) Lucy Moser-Jauslin (Jurgen Moser's daughter, Math), Jerry Berkowitz (son-in-law of Richard, Math), Peter Lax (son-in-law of Richard, Math), Carl Runge (Father-in-law of Richard, Physics and Numerical Analysis). Note that Jurgen and Lucy Moser are a father-daughter combination.
  5. A Band of Blums: Manuel and Lenore (married) and their son Avrim. All do TCS at CMU. Lenore-Avrim is the only mother-son combo I know.
  6. A Geek of Gauss' or A Nerd of Newtons or An Egghead of Eulers or An Ark of Archimedes' are competitive with any of these families. But one person does not a family make.

Wednesday, February 11, 2009

Cleverness Squared

Many articles of interest in the New York Times.








Tuesday, February 10, 2009

How Big is a Trillion?

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


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

Monday, February 09, 2009

Are results about actual constants interesting?

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

He seems to have proven the following:

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

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

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

Friday, February 06, 2009

The Ugly Proof

Alice: Does Carol's proof solve your big open problem?







Thursday, February 05, 2009


  5. Disclosure: Harry Lewis was Bill Gasarch's advisor.

Wednesday, February 04, 2009

Stimulating Science

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

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

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

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

Tuesday, February 03, 2009

While I was Gone

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

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

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

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

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

Monday, February 02, 2009

And you thought the STOC/FOCS deadline were pressure!





BORIS: Two minutes... one minute.


BORIS: I'm fixing it! (nervous)



