Friday, January 30, 2009

When to declare a problem is hard?/Constructive versions of Dilworth's theorem

Why do we think solving P vs NP is hard? There are some matematical reasons (oracles, Natural Proofs, Algebraization) but there is also this notion that many smart peoplet of people have worked on it.

If there is an open problem that not that many people have worked on, even if they are brilliant people, its hard to know how hard it is. I present an open problem of this nature.

Recall Dilworths theorem: If P is a partial order of width w (so the largest set of inc elements has w elements) then there exists w chains that cover P (there are w disjoint linear suborders of P that contain all of P). Dilworths theorem: If P is a partial order of width w (so the largest set of inc elements has w elements) then there exists w chains that cover P (there are w disjoint linear suborders of P that contain all of P). Dilworths theorem: If P is a partial order of width w (so the largest set of inc elements has w elements) then there exists w chains that cover P (there are w disjoint linear suborders of P that contain all of P).

Dilworths theorem is usually proven for the finite case and then, by the usual compactness arguments, holds for the infinite case. So the infinite case has a non-effective proof. The recursive math program tells us to ask the following questions.
  1. Is there a computable function that will, given the Turing machine for a partial order on the set N (input (x,y), output 1 if x&le y, 2 if y &le x, 3 if x and y are incomparable) and given the width w, output a set of w total Turing machines that decide w disjoint chains that cover the partial order.
  2. If not (and the answer is NO) then is there a weaker result that is effectively true?
Here is what is known (roughly):
  1. For every w there is a computable partial order of width w that cannot be covered with ((w+1) choose 2)-1 recursive chains (it can be covered with ((w+1) choose 2) recursive chains). Proven by Szemeredi and Trotter but reported in Recursive Ordered Sets by Henry A. Kierstead, In the book Combinatorics and Ordered Sets. American Mathematical Society, 1986. The proof can also be found in my survey of recursive combinatorics.
  2. There is an algorithm that will, given a computable partial order of width w, find a (5w-1)/4 computable chains that cover it. (An effective version of {D}ilworth's Theorem by Henry A. Kierstead. Transactions of the American Math Society, vol 268, 63--77, 1981.)
The open problem is to CLOSE THAT GAP! How hard is this? I've asked around and it seems that while Hal Kierstead is a brilliant guy and he's had a few brilliant people have working on it, it remains uncracked. Does this mean its hard? Not necc. No matter how Brilliant the people working on it are, I think you need to have a community of people working on a problem for a number of years before you can say WOW, thats a hard problem!.

Thursday, January 29, 2009

Random Thoughts on the Inaugural

RANDOM THOUGHTS on the inaugural. (After this post I will post on politics far less often.)
  1. My colleague Evan Golub went into DC on Tuesday morning of the inaugural and photoblogged his day, much of which was spent on the National Mall awaiting and watching the swearing-in. Here it is: LINK
  2. Most people who I know said they were not going since it was either to cold, to crowded, and they could get a better view on TV (I agree on all three counts). Some said that if they were 20 years younger they would go. But see next item.
  3. The father of a friend of mine went! He is 78 years old! He told me before the inaugural: I didn't think I would see a black man inaugurated as President in my lifetime. I still won't believe it until it really happens. Thats why I want to be there! (He's also a democrat. I wonder what he would have thought if the first black president was a Republican.)
  4. ***SORELLE*** went and blogged about it here.
  5. I actually predicted it would be Obama vs McCain about 2 years ago. (I wish I had put it on record.) The reason: (1) Obama reminded me of Bill Clinton in that he was not known 4 years earlier and had a captivating style. (2) The Republicans tend to give it to someone that is already known, so McCain looked like a good bet.
  6. Predictions for 2012. The Democrats will give the nomination to Obama easily (The last incumbent to not get the nomination was Lyndon Johnson, who didn't want it. Before that it was Chester A. Arthur who didn't want it. Before that it was Andrew Johnson. I don't know if he wanted it.) The Republicans will give it to someone we already know: either Romney or Palin. Perhaps the ticket will be Romney-Palin or Palin-Romney. Are Palin and Romney running? You betcha!
  7. Ben and Jerry's is coming out with an Ice Cream to elebrate the Obama Inagural: Yes Pecan!

Monday, January 26, 2009

Prez Quiz ANSWERS and...

The ANSWERS to my Presidential Quiz are linked to here









Friday, January 23, 2009

Fooling Constant-Depth Circuits

Apparently Mark Braverman has settled a major open question about circuits due to Linial and Nisan. He shows that no poly-logarithmically independent distribution can be distinguished from a truly random distribution by a polynomial-size constant-depth circuit.



In a celebrated 2007 FOCS paper, Bazzi proved the result for the special case for DNF formulas (depth-2 circuits). Razborov recently had a simpler proof of Bazzi's theorem.

Nisan already created specific pseudorandom generators for constant-depth circuits but Braverman's result allows us to use any poly-logarithmically independent set including some that come out of coding theory. While the result doesn't have immediately obvious applications, I expect this result to be a fundamental tool for complexity for years to come.

Scott has a longer take and somehow manages to connect it with quantum computing.

Thursday, January 22, 2009

Presidential Trivia Quiz !

Below is a Presidential Trivia Quiz. Some of the questions are obscure, so it might be more fun to just wait until Monday when I post the answers and then read the questions and answers together.

For those of you who like a challenge, you can take the quiz. There are several ways to do that (1) Take it without looking anything up on the web, or (2) Take it using the web and see how long it takes to finish it or (3) Use the web and score yourself on some combination of how many you get right and how long it took. Its 150 points so perhaps (SCORE) times (1/(NUM OF MINUTES)).

GRADING CRITERIA: Below there are 19 questions totaling 150 points. On the 5 points questions there is no partial credit. All of the 10 point questions ask for a list. If any one item on your answer is wrong then you get 0 points (so DO NOT GUESS!). If you get over half of the items, but not all of them then you get 5 points. If you get all of the items then, of course, you get 10 points.

POLITE REQUEST: Do not post any answers to these questions in the comments.

PERSONAL TRIVIA: This is the post I have spend the most time preparing by far!

  1. (5 points) How many different people have or are been president?

  2. (5 points) How many different people have been vice president?

  3. (10 points) List all of the presidents that have died in office.

  4. (10 points) List all of the presidents who have resigned.

  5. (10 points) List all of the vice presidents that have died in office.

  6. (10 points) List all of the vice presidents that have resigned.

  7. (10 points) List all of the vice presidents that went on to be presidents.

  8. (10 points) What is the max number of ex-presidents alive at the same time? List the times this has happened. Your answer should be a list of statements of the following form: Shortly after X took office there were Y ex-presidents: Z(1), Z(2), ... , Z(Y).

  9. (10 points) What is the min number of ex-presidents alive at the same time? List all the times this has happened. Your answer should be a list of statements that (roughly) say During X's term there was a time when there were no living ex-presidents.

  10. (10 points) List all of the presidents who got a patent.

  11. (5 points) What is the most common first name for a president? List all of the presidents that had that name.

  12. (10 points) List all of the presidents who lived at least 90 years (as of Jan 1, 2009).

  13. (5 points) Who is the only deceased president who was not buried with honors? Why?

  14. (10 points) List all of the presidents who later served in Congress or on the Supreme Court.

  15. (10 points) List all of the presidents that ran again four or more years after leaving office.

  16. (5 points) Name a fictional street gang named after a president.

  17. (5 points) Who was the first president elected after women could vote?

  18. (5 points) Who is the only person who was named after a president, and was played in a movie by an actor who later became president?

  19. (5 points) In what movie did a main character get John Quincy Adams' vice president wrong?

Wednesday, January 21, 2009

Rightful Place



All this we can do. All this we will do. – President Barack Obama, January 20, 2009.

Monday, January 19, 2009

The Dream

Less than two week after I was born, Martin Luther King, Jr. gave his "I Have a Dream" speech. Watch the speech if you haven't seen it yet. I consider it the greatest American speech captured on film.

Today in America we celebrate King's legacy. But King himself gets overshadowed by the realization of part of his dream as Barack Obama becomes the new leader of our nation. No post tomorrow in our recognition of the historic importance of tomorrow's events.

But King's vision has not been fulfilled in academia. We see very few African-Americans particularly in computer science. Why? Blacks certainly still face many more obstacles to succeed in academia. Those that succeed perhaps feel they can do more good as political or business leaders.

I appreciate the efforts of those, like my co-blogger Bill Gasarch, who make the effort to visit historically black colleges to talk to and recruit students or take part in the Richard Tapia Celebration of Diversity in Computing. But we have a long way to go.

King's dreams don't truly get fulfilled until we no longer have these discussions, when African-Americans can and do follow their paths in all aspects of society. Obama's inauguration is a big step, but full equality still, unfortunately, remains a dream.

Friday, January 16, 2009

Planes. Fellows. Power.


Suresh posts about the new ACM Fellows. Congrats to all!



Thursday, January 15, 2009

Amitabh Varshney (Graphics Faculty at UMCP) emailing me the following:
Someone told me a while ago that there are some theory conferences in which members of the program committee are not allowed to submit papers. Is this really true? Does this still happen?
My first impulse was that theory conferences largely do not allow PC mems to submit (I knew that STOC, FOCS, COMPLEXITY did not, and that COLT did). By asking people (I could not find this info on websites) I have compiled the following list. Corrections and additions are welcome. PC stands for program committee.
  1. Do not allow PC mems to submit: STOC, FOCS, ICALP, MFCS, COMPLEXITY, SODA, RANDOM, APPROX, SoCG
  2. Up to the PC: LICS
  3. Allow it but there are various restrictions: CRYPTO, EUROCRYPT, RECOMB (e.g., only two such submissions per person, or some complicated thing having to do with if students are co-authors. The exact rules change from year to year.)
  4. Allow it with no restrictions: COLT, ALT, ISMB (biocomp), WABI (biocomp) EC (electronic Commerce)
  5. My friends outside of theory tell me that allowing submissions from PC mems is the norm. Note above quote from Amitabh Varshney.
Now some RANDOM comments on this. I can submit the comments to RANDOM unless I'm on the PC.
  1. Reason to allow it: if it is not allowed then people might decline to be on the PC.
  2. Reason to not allow it: avoid conflict of interest and the appearance of conflict of interest.
  3. For those that do allow it, the person who submitted is not allowed to be involved in the discussion. This works pretty well especially with meeting over-the-web.
  4. From what I've seen and heard there is not a problem with the PC mems having an advantage. In fact, RECOMB explicitly says that a PC mems paper has to meet a higher standard. For other conferences this has been the de facto rule.
  5. When COLT began the area of Learning Theory was small so they allowed PC mems to submit, else there would be too small a pool of people to submit. This is no longer true, but the rules live on.
  6. The first few years of COMPLEXITY (then called STRUCTURES) the PC mems were allowed to give invited talks. This struck me as being a good way to reward the PC mems. But if they all want to do it, that is too many invited talks.
  7. In COMPLEXITY this issue has not been revisited- it is not brought up at business meetings. According to Jeff Erickson's SODA BUSINESS MEETING BINGO it does come up at SODA business meetings. I've heard it also come up at SoCG business meetings.
  8. If you let PC mems submit they you can have a large PC without depleting the pool of people who can submit.
  9. I have no strong opinion on this issue. I'll leave that to the comments.

Wednesday, January 14, 2009

So You Think You Settled P verus NP

  1. You are wrong. Figure it out. Sometimes you can still salvage something interesting out of your flawed proof.
  2. You believe the proof is correct. Your belief is incorrect. Go back to step 1.
  3. Are you making any assumptions or shortcuts, even seemingly small and obvious ones? Are you using words like "clearly", "obviously", "easy to see", "should", "must" or "probably"? You are claiming to settle perhaps the most important question in all of mathematics. You don't get to make assumptions. Go back to step 1.
  4. Do you really understand the P versus NP problem? To show P≠NP you need to find a language L in NP such that for every k and every machine M running in time nk (n = input length), M fails to properly compute L. L is a set of strings. Nothing else. L cannot depend on M or k. M can be any program that processes strings of bits. M may act completely differently than one would expect from the way you defined L. Go back to step 1.
  5. You submit your paper to an on-line archive. Maybe some people tell you what is missing or wrong in your paper. This should cause you to go to step 1. But instead you make a few meaningless changes to your paper and repost.
  6. Eventually people ignore your paper. You wonder why you aren't getting fame and fortune.
  7. You submit your paper to a journal.
  8. The paper is rejected. If you are smart you would go back to step 1. But if you were smart you would never have gotten to step 7.
  9. You complain to the editor that either the editor doesn't understand the proof or that it is easily fixed. You are shocked a respectable editor or journal would treat your paper this way.
  10. You resubmit the paper, appeal, try other journals all to no avail.
  11. You are convinced "the establishment" is purposely suppressing your paper because our field would get far less interesting if we settle the P versus NP problem so we have to keep it open at all costs.
  12. If I tell you otherwise would you believe me?

Tuesday, January 13, 2009

Best Job?

Nicole Immorlica pointed me to a Wall Street Journal article about a ranking of 200 jobs by CareerCast. Number one: Mathematician.

So what is a mathematician? Does anyone actually get hired to be a mathematician as opposed to a professor, actuary, statistician or quant. The site defines mathematician as

But then why are jobs 2 and 3, actuary and statistician, listed as separate jobs.

Since the list does not contain computer scientist, mathematician is the closest to what I do. So I have the best job! Awesome. Thought I'd still rather be commissioner of Major League Baseball.

The Rating Methodology uses several categories: Work Environment, Physical Demands, Stress, Income and Outlook. The ratings lack a "fun factor" in any of these categories. Which sounds more fun: Actuary or Lumberjack (number 200 job)?

Monday, January 12, 2009

A Complete History of the LVDW conjecture

When you first make a conjecture you don't know if it will be important or interesting or both or neither. In the case below it was solved quickly, the answer was not interesting, and I doubt anymore will come of it. But, I did get a blog posting and some nice exercises for a class out of it.

Recall: VDW theorem is the following
For all k, for all c, for all c-colorings of N (the naturals) there exists a monochromatic arithmetic progression.
I was looking at a variant of this:

Definition: An arithmetic sequence is large if it is at least as long as its least element. The following are large arithmetic sequences: (1), (2, 10), (4,5,6,7). The following is NOT large arithmetic sequences: (100,102,104,...,118).

Note that for any c-coloring of N there is (trivially) a large monochromatic AP: just take (1). But what if we start coloring the naturals starting at k?

LVDW CONJECTURE: for all k, for all c, for all coloring c-colorings of (k,k+1,k+2,...) there exists a large monochromatic AP.

Why do I care? There is a Large Ramsey Theorem which is similar and is true. It is proven from the infinite Ramsey Theorem. It is of interest because this theorem is not provable in Peano Arithmetic (the associated functions grow faster than any function definable in PA). This leads to the following questions: I was hoping that LVDW CONJECTURE was true but ind of PA.

Alas, Andy Parrish (was Brilliant ugrad at UMCP in CS, is now brilliant grad at UCSD in math) proved LVDW CONJECTURE false. I leave it as an exercise.

There is a question that remains, though it just be equivalent to getting bounds on VDW numbers.

Definition: Let g:N &rarr N An arithmetic sequence is g-large if it is larger than g of its least element.

For which sequences of functions fc is the following true: for all k, for all c, for all coloring c-colorings of (k,k+1,k+2,...) there exists a fc-large monochromatic AP.

We know there is such a sequence by the ordinary VDW theorem (exercise).

Friday, January 09, 2009

Conferences Abroad

Samir Khuller guest posts about having conferences in exotic locations.



Thanks to Moses Charikar and Sudipto Guha for comments.

Thursday, January 08, 2009

Sorting a Partial Order

I liked the SODA2009 paper Sorting and Selection in Posets since it makes you look at ordinary sorting in a new way.

What does it mean to sort a list? We usually think (correctly) that we take a list of ordered objects and put them into an ordered list. How to extend this to partial orders? We need to re-look at total orders.

Say that making a comparison between elements of the ordered set is HARD Then you want to make as few as possible. But you want to, when you are done, have a data structure that makes comparisons easy. Hence we view sorting as follows:
Given a set A of n elements from a totally ordered set come up with a data structure of size O(n) such that the operation Given x,y &isin A which one is bigger? can be done in O(1) time. While setting up the data structure you would like to to do this with as few comparisons as possible. We will assume that comparing two elements of {1,...,n} is easy.
Given a sorted array you can easily obtain such a data structure: pair each element with its index in the array. To compare x,y quickly just compare index(x) and index(y). Note that we think of comparing numbers in {1,...n} as easy but comparing elements of the ordered set as being hard.

The papers Sorting and Recognition problems for Ordered Sets (SICOMP 1988, Faigle and Turan) and Sorting and Selection in Posets (SODA 2009, Daskalakis, Karp, Mossel, Riesenfeld, Verbin) study this issue.
Definition: Let P=(X,<) be a partial order.
  1. A chain decomposition of P is a partition of X into sets each one of which is totally ordered under < .
  2. A chain merge data structure for P is a chain decomposition together with the following. For each x &isin X, the following information: (1) which i has x &isin C_i, and (2) for all j, what is the largest element in C_j that is < x. It is easy to see that from such a data structure you can do comparisons in O(1).
  3. The width of P is the min number of elements in a chain decomp.
  1. Faigle and Turan showed that if P has width w then it can be sorted in O(wnlog n) comparisons. (Can also see Daskalakis et al paper for this.)
  2. Daskalakis et al showed that if P has width w then it can be sorted in O(n(w+log n)). They use the Chain Merge Data Structure. This bound matches the info-theoretic min.

Wednesday, January 07, 2009

SODA and Me

There have been 23 IEEE Conferences on Computational Complexity and I have been to all of them. There have been 20 ACM-SIAM Symposiums on Discrete Algorithms and I have been to none of them. Yesterday Bill talked about the joys of SODA. So why haven't I gone?

I have nothing against SODA. The conference has strong papers and researchers. Algorithms is an important area of theory. But algorithmic results just don't excite me in the same way that a beautiful complexity result does. I don't mind a good algorithms talk every now or then but I don't think I could take three straight days of them.

When I applied for graduate schools my boss in Cornell Computer Services tried to talk me out of being a theorist. "Do you really want to spend your life shaving log factors off of running times?"

"Yes, I do," I replied. But in fact I don't and I didn't.

I have had two SODA submissions, both accepted to the 2003 conference in Baltimore. Right before SODA that year I was visiting Bill in College Park, south of Baltimore. As I drove back to New Jersey I pondered taking a right off the highway into the conference. But then common sense took over and I drove on.

Tuesday, January 06, 2009

I went to SODA 2009!

I just got back from SODA 2009 in New York (Symposium on Discrete Algorithms). In later posts I will describe some of the interesting papers that I saw, Today I'll just note some things.
  1. Why did I go? One of the papers I covered in my grad class (On the Power of two, three, or four probes by Alon and Feige) was a SODA2009 paper, so I looked at the schedule and spotted 10 more papers that I was interested in. AND it was close AND my parents live in NY so no hotel fee AND school hasn't begun yet for me so no problem with missing appointments.
  2. They had coffee but no food and no lunch. Since I recently was local organizer for COMPLEXITY (with Richard Chang and Marius Zimand) I KNOW how expensive food can be, so I have NO complaint here. I may never be able to complain about a conference again (unless its REALLY bad in which case I can complain more legit, or unless they claim to be refereed but are not).
  3. They did not have proceedings! They had all of the papers on line at the SODA website, and they had a CD. PRO: no bulky proceedings to take home, might save paper. CON: Hard to browse through proceedings at conference or at home. This will get easier with technology. MY OPINION: Good Idea.
  4. For me the talks were easier to understand than those at Complexity. This is because those that were on algorithms, describing the problem was reasonable (in complexity just describing the problem is hard) and those that were on complexity or combinatorics or some odd-ball mathematics, were the ones I was familiar with so could follow.
  5. There were around 400 people there!
  6. Was it worth going- YES. Will I go again- If the stars align themselves properly again then I will.
  7. Michael Sipser once told me Its good to look at algorithms once in a while as a sanity check on your lower bounds.

Monday, January 05, 2009

Stephen Kleene: Not A Regular Guy

The great logician Stephen Kleene was born one hundred years ago today in Hartford, Connecticut. No single person affected a typical introductory theoretical computer science course more than Kleene. Kleene gave us
  • Regular expressions and their equivalence to langugages accepted by finite automata. That's why we call them Regular Languages.
  • Kleene Closure, the * operator in regular expressions. L* is the set of all finite concatenations of strings in L. Source of great homework problems, for example: Show P is closed under Kleene closure.
  • A recursive definition of Turing's languages, the reason they are often called Recursive Languages (though not without controversy).
  • The terminology Church's thesis that we now call the Church-Turing thesis (though more controversy).
  • The arithmetic hierarchy, a forerunner of our polynomial-time hierarchy.
  • The Smn theorem that one can uniformly hardwire part of the input into the code of a Turing machine.
  • The recursion theorem (sometimes called the Kleene fixed point theorem) that informally says no matter how nasty the virus, some program remains unscathed.
and much more.

Klenne passed away January 25, 1994 in Madison, Wisconsin where he spent most of his academic career.

Friday, January 02, 2009

Randomness in Voting

Every voting scheme has the property that in some scenario a change of a single vote can change the outcome. When a major election has a very close result, like the current senate race in Minnesota or the 2000 presidential race in Florida, every vote gets scrutinized very carefully and the process can drag out for months.

This scrutinization ignores the randomness factor. Some people got stuck in traffic or maybe had some emergency that prevented them from voting. Some people went to the wrong voting area or their registration got lost. Some people just plain filled in the wrong oval, voting for the wrong candidate. These problems are rare and roughly cancel themselves out but in a very close election like Minnesota the randomness greatly outweighs the disputed ballots. Yet because of the hard cut-off the scrutinized ballots get the most attention.

I suggest we eliminate the hard-cut off by adding our own randomness. For simplicity suppose we had two candidates, Al and Norm, who received x and y votes respectively. We flip z=x+y uniform random coins. If the number of heads is at most x we declare Al the winner and Norm the winner otherwise. If x > z/2+ 10 z1/2 then this process would make Al the winner almost all the time. But as x and y get very close the probability that Al wins approaches 1/2. Since a change of a few disputed votes won't affect the probability dramatically, we won't have so many battles over so little.