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 (5^w-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!.

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!

Prez Quiz ANSWERS and...

The ANSWERS to my Presidential Quiz are linked to here

First I'll answer the questions raised in the comments of the presidential quiz post.

1. Who served the most time as President and VP combined?
   
   Richard Nixon was VP for 8 years (Jan 1953-Jan 1961) and Prez for 5.5 years (Jan 1969-Aug 1974) for a total of 13.5 years. In second place is FDR who was Prez for 12 years 1.5 month (Mar 4, 1933-Apr 12, 1945) In third place is a tie between John Adams, Thomas Jefferson, and George Bush Sr. who all served for 12 years. (Adams and Bush did 8 years VP, 4 years Pres, while Jefferson did 4 years VP, 8 years Pres.)
2. Who was the last person before Bush Sr. who was elected President while holding the office of VP?
   
   Martin van Buren was sitting VP in 1836 and got elected. (He was Andrew Jackson's VP.)

There was one question (actually more) that were on the Prez Quiz originally but I removed. The reasons why they were removed point to some issues.

QUESTION: Who was the first female to run for president of the United States?

ANSWER: Historians say it was Victoria Chaflin Woodhull, Equal rights party, ran in 1872 and 1892. She did go around the country campaigning. This was before women could vote. Fredrick Douglas was her vice President. While historians acknowledge that she was the first female to run for president, under some stricter criteria her 1872 run does not count. Her name was not allowed to appear on any ballots and she got no votes. She died in 1927 and hence lived to see women get the vote and use it to elect Warren G. Harding. Oh well.

Under a stricter criteria the answer would be Belva Ann Lockwood who ran in 1884 and 1888. She was on some ballots and got 4100 votes. She died in 1917 and hence did not live to see women get the vote.

I removed the question because its ambigous. What does run mean? You can read a list of various people who may qualify at this website which has women who ran for president in any country.

History is full of ambigous questions. Discussing them is of interest. Seeing what prior generations thought of history may tell us about that generation. However, I prefer fields with definite answers.

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.

A r-independent distribution over binary strings of length n means that for every set of r bits are uniformly distributed over the 2^r possible values for those bits. We can create r-independent distributions using O(r log n) truly random bits.

Braverman shows that no depth-d size-m circuit of AND, OR and NOT gates can distinguish between a truly uniform distribution and any r-independent distribution with r = (log m)^O(d2).

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.

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?

Rightful Place

The state of our economy calls for action: bold and swift. And we will act not only to create new jobs but to lay a new foundation for growth.

We will build the roads and bridges, the electric grids and digital lines that feed our commerce and bind us together. We will restore science to its rightful place and wield technology's wonders to raise health care's quality and lower its costs. We will harness the sun and the winds and the soil to fuel our cars and run our factories. And we will transform our schools and colleges and universities to meet the demands of a new age.

All this we can do. All this we will do. – President Barack Obama, January 20, 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.

Planes. Fellows. Power.

It was a common joke to point out how people really overestimate low or zero probability events. Why in the pre-flight briefing do the flight attendants teach us not one but two ways to inflate our life vests when there has never been a successful emergency water landing of a commercial airplane? Never. Ever. Until yesterday.

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

Kirk Pruhs asks us to plug the Workshop on the Science of Power Management.

In particular it would be interesting to see if some interesting complexity theory could be built for energy/power as a resource instead of the usual complexity of space/time. On one hand, it is not immediately obvious how to do this as energy seems quite different than space/time, e.g. I guess there is no energy hierarchy theorem analogous to the space/time hierarchy theorems. On the other hand, I would be surprised if there is just no interesting complexity theory of energy.

In the Clinton administration it helped to make research relevant to the Internet. In the Bush administration it helped to make research relevant to national security. In the Obama administration it will help to make research relevant to energy and the environment. The beauty of complexity: It's always relevant.

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.

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 n^k (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?

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

Applies mathematical theories and formulas to teach or solve problems in a business, educational, or industrial climate.

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

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 f_c is the following true: for all k, for all c, for all coloring c-colorings of (k,k+1,k+2,...) there exists a f_c-large monochromatic AP.

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

Conferences Abroad

Samir Khuller guest posts about having conferences in exotic locations.

During the SODA Business Meeting I was a bit alarmed at some of the suggestions made for where the conference should be held in future years—some of the locations that even received substantial support were Paris and Buenos Aires. I have nothing against these locations, in fact Paris is one of my favorite cities to visit and Buenos Aires is high up on the places I want to visit. (I also want to visit Chile and Antarctica!) I wanted to make a few remarks about exotic locations.

1. The cost of sending students to conferences is already non-trivial. At least with NYC the travel costs are low for many students between DC and Boston. For faculty who are trying their best to stretch limited travel funds to pay for several students, moving the conferences to exotic locations makes life quite difficult. I would like to see major US conferences held in places where there is a substantial presence of students—Boston, Bay Area, NY, DC to name a few. We should move the conferences around, so that each student has an opportunity to attend a major conference in their area during their studies. If someone made a convincing argument about the benefit to Argentina theory grad students that would be an argument for Buenos Aires.
2. At a conference I spend 90% of my time indoors. For the 2 hours I spend outdoors each evening, it almost does not matter where one is. There are nice cities in the US to visit and NY, DC and San Francisco have emerged as popular locations, drawing a big audience. If we moved the conference or even alternated between the east and west coasts, that would be terrific.
3. There are visa issues for students on F1 visas making it tricky for them to attend meetings outside the US. For some students getting a visa involves them visiting their home country first, since they cannot get a re-entry visa to the US from some random country. There are already a lot of European theory conferences (SWAT, ICALP, ESA, STACS) to name a few. There are fewer conferences in N. America (STOC, FOCS, SODA). We had one STOC in Greece and one FOCS in Rome already. The other theory meetings such as PODC, PODS, LICS, SPAA already move around between Europe and N. America, why are we then taking our major conference and trying to move it to locations that make it harder for our students to attend?

Finally, if people suggested cities after checking prices at the major hotels that would be useful. While Paris has some reasonably priced small hotels, it could easily be that the large hotels are really expensive. We could then cast a more informed vote. The SIAM Disc. Math Conf. in contrast has extremely low registration fees and is usually held at a Univ campus during the summers.

Thanks to Moses Charikar and Sudipto Guha for comments.

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.

RESULTS:

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.

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.

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.

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

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 z^1/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.