A candidate for a new Millenium Problem

In a prior post I wrote that the Erdos-Turan Conjecture should be a Millennium problem. Today I am going to (1) suggest a generalization of the Erdos-Turan Conjecture should be a Millennium problem instead, and also suggest (2) a far harder problem be another candidate. For some history see here. (This is an excerpt from my still-being-written book on VDW stuff- so if you find a mistake or suggestions please comment or email me.)

Recall the poly VDW theorem:

Let p₁,...,p_k ∈ Z[x] such that p_i(0)=0. Let c ∈ N. There exists W=W(p₁,...,p_{_k};c) such that for any c-coloring of {1,...,W} there exists a,d such that a, a+p₁(d), ..., a+p_k(d) are all the same color.

Much like VDW's theorem was before Gowers result, (1) there is a proof that gives bounds that are not primitive recursive (Walters proof) (2) there is a density-type theorem that does not give good bounds, (3) there is a proof by Shelah that gives primitive recursive bounds, but they are still quite large.

We make the following conjecture which we hope will lead to better bounds on the poly VDW numbers.

CONJ: Let p₁,...,p_k ∈ Z[x] such that p_i(0)=0. If Σ_{x ∈ A} 1/x diverges then there exists a,d such that

a, a+p₁(d), ..., a+p_k(d) are all in A.

1. The case where all of the polynomials are linear is often called the Erdos-Turan Conjecture. It is still open.
2. The following is a subcase that is orthogonal to the Erdos-Turan Conj: If Σ_{x ∈ A} 1/x diverges then there exists two elements of A that are a square apart.
3. Green and Tao showed that the set of primes have arb. large AP's. Then Tao and Ziegler showed the following: Let p₁,...,p_k ∈ Z[x] such that p_i(0)=0. There exists a, d such that
   
   a, a+p₁(d), ..., a+p_k(d) are all primes.
   
   SO the CONJ is true for a particular set of interest.

We also pose a question which is more interesting but likely much harder:

If A is a set then let d_A(n) =|A ∩ {1,...,n}|/n. The lim sup_{n → ∞} d_A(n) is the upper positive density. We will be interested in the function d_A(n).

QUESTION: Let p₁,...,p_k ∈ Z[x] such that p_i(0)=0. Find functions e₁(n) and e₂(n) (not that far apart) such that e₁(n) ≥ e₂(n), and the following occurs:

1. If for almost all n, d_A(n) ≥ e₁(n) then there exists a,d such that a, p₁(d),...,p_k(d) ∈ A.
2. There exists A such that, for almost all n, d_A(n) ≥ e₂(n), and there is NO a,d such that a, p₁(d),...,p_k(d) ∈ A.

For the case of 3-AP's the following are known:

1. If for almost all n d_A(n) ≥ (log log n)⁵/log n then A has a 3-AP. (See this Tom Sanders paper.)
2. There exists a set A such that, for almost all n d_A(n) ≥ 1/n^{\sqrt(log n)} and A has no 3-APs (See Michael Elkin's paper for a slightly better result that I didn't have the energy to typeset.)

These two functions are NOT close together. So even in the case of 3-AP's we do not know the answer. I want to know the e1,e2 for ALL finite sets of polynomials with 0 constant term. We've got our work cut out for us.

It is my hope that progress on the question will lead to better bounds on some poly VDW numbers. A similar question DID lead to better bounds on the VDW numbers.

Moneyball

I saw Moneyball over the weekend. This movie gives a fictionalized account of the how the general manager of the 2002 Oakland A's used the right kind of statistics to build a strong team with a low budget. This article on the GM Billy Beane gives a nice follow-up to the movie.

A bit surprising one can get a good movie about the math in baseball. Moneyball was based on the book by Michael Lewis with a screenplay co-written by Aaron Sorkin who also wrote the screenplay to the Social Network. Sorkin writes nerdy things well.

Moneyball is really a computer science movie. It's not about the computers themselves which play a small role, but its about taking a large amount of data and deriving the conclusions that help make the crucial decisions in developing the team.

You can also see the difference in computer science over the last decade. At the time of Moneyball, people would try many statistical models and test them out. These days via Machine Learning we give the computer the data and the results and the computer determines the right models.

Oddly enough Billy Beane's actions led to an even greater separation between the large and small market teams. The statistical ideas that Beane pushed have been adopted by the other teams. Now we've hit an equilibrium so the teams that spend more win more as well.

Oddly the New York Times ran an editorial piece Not-So-Smart Cities by Greg Lindsey yesterday arguing that cities shouldn't rely on these kinds of statistics for planning because of a failed project from the 60's. Sounds like Lindsey needs to see Moneyball.

Mahaney's Theorem

Bill has a lot of posts where he questions whether to teach Mahaney's theorem in a graduate complexity class. Since it is one of my favorite theorems and most of you young folk won't see a proof in your complexity classes, I'll give it here. This proof is not the original of Mahaney but based on a paper by Ogihara and Watanabe.

Mahaney's Theorem: Let c be a constant and A be set such that for all n, A has at most n^c strings of length n. If A is NP-complete then P=NP.

Proof: We define the left-set of SAT as follows: Let B = { (φ,w) | φ has a satisfying assignment a with a ≤ w in lexicographic order}. We'll restrict ourselves to w that are (not necessary satisfying) assignments for φ.

Assume φ is satisfiable and let a' be the lexicographically smallest satisfying assignment. We have (φ,w) is in B iff w ≥ a'.

Since B is in NP by assumption B reduces to A via some function f computable in polynomial-time, (φ,w) is in B iff f(φ,w) is in A.

Fix φ and n and let m=n^k bound the number of strings in A of any length that f(φ,w) could query. Pick w₀ < w₁ < w₂ < … < w_m+1 evenly spaced from each other.

Let z_i = f(φ,w_i) for each i. Note that if z_i is in A then z_j is also in A for all j ≥ i.

Case 1: z_i = z_j for some j > i. We know a' cannot be between w_i and w_j.

Case 2: All the z_i are distinct. There are only m elements in A so z₁ is not in A and a' cannot be between w₀ and w₁.

Either way we have eliminated a 1/(m+1) fraction of the possible assignments.

We repeat the process choosing the w_i equally spaced among the remaining possibilities and eliminate another 1/(m+1) fraction of those assignments. We continue O(mn) times until we narrow down to a set S of m+1 possible assignments.

If φ is satisfiable then a' is in S so at least one assignment in S and will satisfy φ. If φ is not satisfiable then none of the assignments in S satisfy φ.

By trying all the assignments of S and seeing if they satisfy φ, we get a polynomial-time algorithm to determine if φ is satisfiable. Since Satisfiability is NP-complete we have P = NP.

Where do theorems go to die?

(Joint post by Bill Gasarch and Daniel Apon)

Recently I (Daniel) reviewed Dexter Kozen's Theory of Computation (it was AWESOME). You can find the review here. Many of the topics were standard but some we (Bill and Daniel) suspect are not covered in any complexity class (well... maybe in Dexter's). This DOES NOT detract from the book, however we now raise the question:

Where do Theorems go to die?

In some eras there are some theorems that are taught in EVERY basic grad complexity courses Then all of a sudden, they are NOT taught at all. (Both the EVERY and the NOT are exaggerations.)

1. The Blum Speedup theorem: In the 1970's EVERY comp sci grad student knew it. In the 1980's EVERY theorist knew it. In the 1990's EVERY complexity theorist knew it. In the 2000's (that sounds like it means 2000-3000) EVERY... Actually NOBODY knew it, except maybe students who took Dexter's class. I doubt Blum teaches it anymore. Blum's speedup theorem was proven before Cook's theorem when people were still trying to get complexity right. Blum has since said Cook got it right! Even so, Blum's Speedup theorem should be in the preface to God's book of algorithms (See here) as a warning that there might not be an optimal algorithm.
2. The Complexity of Decidable theories (e.g, Presburger, WS1S, S1S, S2S). We all know that by Godel's theorem the theory of (N,+,times) is undecidable. There are some subtheories that are decidable. However, the decision procedures are complete in various rather high up classes (WS1S is provably not primitive recursive). This material I (Bill) learned from Michael Rabin (who himself proved S2S undecidable) in 1981 but my impression is that it is not taught anymore. Was it ever widely? We think that students should know the STATEMENTS of these results, because these are NATURAL problems (Bill did the capitalization) that are complete in classes strictly larger than P. (See the second conversation here for comment on that.) One of us thinks they should also know the proofs.
3. omega-Automata. This is used to prove S1S decidable and we've heard it is used in fair termination of concurrent programs. Sounds like it should be more well known. But it is rare to find it in a complexity cousre. It may well be taught in other classes. (I (Bill) touch on it in undergrad automata theory.)
4. Jon Katz is pondering not teaching Ladner's theorem!!! The students should surely know the result (YES, and stop calling me Shirley) however, should they know the proof?
5. Spare Sets: Bill Blogged about no longer doing Mahaney's Theorem Karp-Lipton is still used A LOT, but Mahaney's theorem is not really used at all. Daniel thinks Mahaney's Theorem is AWESOME, however Daniel is bright eyed and bushy tailed and thinks ALL of this stuff is AWESOME.
6. Computability Theory: Friedberg-Muchnik, Arithmetic Hierarchy, Analytic hierarchy, Recursion Theorem. This is like Blum Speedup- this material used to be better known to complexity theorists but is hardly taught to them anymore. It IS of course taught in courses in computability theory. But such courses are taken by complexity theorists far less often then they were. When I (Bill) tell someone there are c.e. sets that are not decidable and not complete! they say Oh, just like Ladner's theorem. Its the other way around, Ladner's result came far later.
7. Part of this is that Complexity theory has changed from Logic-Based to Combinatorics-Based (see post on CCC Call for papers) We don't teach Blum Speedup (and other things) any more because we have better things to teach. However, are there results that the students should know even if the fields they come from are dead? YES, and Ladner's theorem is one of them.

Who decides such things? Textbook writers for one. A Proof Theorist who worked on lower bounds for Resolution told me he hopes that Arora-Barak's book would include this material. He even said If it does not, the field will die. Is this true? If so then Arora and Barak have more power than they realize.

Conferences Again

Lots of conference news and views going around. Let's sort it out.

FOCS early registration deadline is September 29th, fast approaching. Deadline for applying for student support is this Thursday September 22. Apply even if you don't have a paper there and take the opportunity to attend one of theory's most important meetings.

Also the STOC 2012 submission deadline is still November 2. There was a mistaken deadline listed on a theory events site.

The SODA 2012 accepted papers (and links to Arxiv) are out. Program Committee Chair Yuval Rabani explained the PC process. Seems pretty much along the lines of PCs I've been apart of. I wished they did penalize people who had poorly written papers, otherwise there's little incentive to write well. I'm also not a big fan of the "pet paper" idea, people tend to choose papers of their friends and colleagues.

Michael Mitzenmacher posted about the number of good papers not accepted and whether SODA should accept more (an issue at most of our major conferences). In this blog, Sami Khuller guest posted about whether it makes sense to have SODA in Japan. There are a handful of SODA accepts with primarily Japanese and other Asian authors but the vast majority of the authors are US-based.

Some of the comments on Khuller's post talked about having a virtual conference. How about this idea: We don't bother meeting and just collect the accepted papers into a single volume. We can give this idea an innovative name like a "journal".

In this month's CACM article, Moshe Vardi complains about the quality of conference talks. (I like the "journal  that meets in a hotel" quote but it didn't originate with me). You see this at STOC and FOCS too, people giving a talk only to other specialists in their field instead of aiming for a general audience.

Most of you readers know my position on conferences, that we need to get conferences out of the ranking business in CS so conferences can instead play their role of bringing community together and escape from the explosion of conferences just to give people who were rejected from another conference a place to submit their papers.

Happy Constitution Day

September 17th officially is known in the United States as "Constitution Day and Citizenship Day" but is celebrated today because the 17th this year falls on a weekend. I  have nothing but love for the our Constitution. Not only does the Constitution and its amendments provide the great freedoms we have in America but it also shows how to balance states of different sizes with a strong central government. The EU could do worse than by following its example.

What bothers me is a law that Robert Byrd snuck into an omnibus spending bill in 2004.

Each educational institution that receives Federal funds for a fiscal year shall hold an educational program on the United States Constitution on September 17 of such year for the students served by the educational institution.

With a few exceptions like the military academies, US universities are either run by the states, municipalities or are private institutions. It defeats the whole point of the Constitution for the Federal government to be dictating to US universities what educational programs must be held when.

Most universities do the minimum. Northwestern just points students to a website with Constitution related information and videos.

To help all of you celebrate Constitution Day here is the great preamble as I learned it as a kid.

Conventions in Math- just to make the rules work or more?

1. Why is

   a^1/2 = sqrt(a)?

   true? To make the rule

   a^x+y=a^x a ^y

   work out.
2. Why is

   (∀ x ∈ ∅)[P(x)]

   true? To make the rule

   (∀ x ∈ A ∪ B)[P(x)] iff (∀ x ∈ A)[P(x)] AND (∀ x ∈ B)[P(x)]

   work out.
3. Why is the sum over an empty index set equal to 0 and the product over an empty index set equal to 1? Same reason- it makes various math laws work out.

For the second and third item on the above list I would say its not JUST to make some rule work out, it also makes sense. But the first item, that a^1/2 = sqrt(a), seems to only make sense in terms of making a rule work out and not for any other reason. I have no objection to the rule; however, if you have a REASON other than it makes the rules work for this convention, please leave a comment.

Imagine

Looking back, it's pretty amazing how new technologies like Google, cell phones, Facebook and Twitter have changed society in completely unexpected ways. Let's play a game with an up and coming technology that will surely change society but it is not clear yet how.

We already have the technology for autonomous cars, cars that can drive themselves with no needed changes to roads or other cars. By 2020, this technology will be cheap enough to be built into most new cars.

1. When will society and laws be accepting of autonomous driving? Will we ever be able to get rid of the drivers seat?
2. What will cars look like when there is no driving seat?
3. Will there be a major elimination of jobs of taxi and truck drivers? Is this a bad thing?
4. Will we still need parking right near our destination? Will driveways disappear?
5. Once most cars are autonomous will they be networked for better coordination? Will we see the elimination of now unneeded street lights and signs? Will there be privacy concerns?
6. These cars will stop or serve around obstacles. How do we stop pedestrians from just walking out in front of cars knowing they will stop?
7. Will people mostly own cars or just rent one that happens to be close by?
8. Suburbia exists because of the automobile. Will an autonomous car change the nature of suburban life?
9. Most importantly, what is the big societal change that will occur that we can't imagine right now.

Guest Post on Conference Locations

(Samir Khuller Guest Post.)

On Conference Locations:

I recently looked at Orbitz for fares to Japan for SODA 2012 in Jan. The round trip fare from DC to Tokyo is close to $1700. Together with the train to Kyoto, we are looking at a $2000 travel cost to attend SODA for 3-4 days. Together with the registration and hotel, I am sure the cost will exceed $3000. I wonder how many people will be able to attend this conference? In times of declining budgets, we should make these decisions after careful thought since our travel budgets are only shrinking. In 2012, all conferences are likely to be expensive to attend -- SODA in Kyoto, CATS in Melbourne, STACS in Paris, Complexity in Porto, ESA in Slovenia, ISMP in Berlin, ICALP in UK, SWAT in Finland, LATIN in Peru, SIGMETRICS in UK, FST&TCS in India, not to mention all those exciting Bertinoro and Dagstuhl meetings. At least STOC is in NYC!

I am sure that the same dilemma is faced by people in the far east when we hold conferences in the US. However, I will be curious to know what the numbers look like. Are we going to reduce costs for 25 students who otherwise might not be able to attend SODA because its not in Japan (I hope this NOT the case, and the numbers look much better)? However, at the same time we might be making the cost prohibitively high for 100 students who could have attended the conference, but are not going due to the high cost. Wait, we did this once. We had FOCS in Rome! According to this blogpost it looks like only 172 people registered for FOCS 2004. Given that most likely 100 of the attendees were authors, the drop in attendance of non-authors is by a factor of 50% since FOCS most likely gets close to 230 attendees.

I am for the argument that once in a while its not bad to move a conference around to help people attend who normally might not; but we could explore other ways of helping such people attend. Once we move a conference to a place where not much local population will attend, its a problem (FOCS 1991 in Puerto Rico). SODA in Israel or Germany makes more sense to me since a large part of the algorithms community is from those places. One way to help defray the costs is to use part of the conference funds to help provide travel support for people whose cost to attend would be too high. Co-locating meetings might benefit us more (FCRC, ICALP-STOC 2001 in Crete). If we want to maximize interaction among people we should aim to have one large meeting as opposed to lots of small ones - the ISMB and ISMP conferences do this very well. More edges in a clique of 1000 nodes than 10 cliques of 100 nodes each. ALGO in Saarbrucken makes sense to me. High density of researchers, several meetings are combined into one along with ESA. Frankfurt is easy to get to from a lot of places in the world (except for the folks in Australia, NZ and Hawaii), and there is great train service from the airport to Saarbrucken.

One of the cheapest conferences I attended was the SIAM Conf. on Discrete Math at the University of Toronto campus. Very low registration cost and we could stay on campus in the dorms for $20/day. Having looked into (and having organized) conferences recently, I know that the dinner can cost $100/person, and the coffee break $20/person. Do we really need to have academic conferences at such large hotels and hard to reach places? Why not have a conference that encourages participation, as opposed to one that discourages it? Even I would not mind a conference in space, lets see if NSF would approve "foreign travel" for that one.

I am going to have to start a new US "regional" conference, that I can afford to send my students to! It will be held on a university campus and the reg fee will be $100/student; and it will be cheap to get to. At least for the years when SODA is not in the US, such a meeting might be a success.

NOTE: I have nothing against Kyoto and Rome, they are among my favorite places in world.

Next in the sequence

When I posted on sequence problems here some people said that they did not have unique answers. Many problems FORMALLY do not have a unique answer, but common sense and simplicity lead to a unique answer. This recently happened on Jeopardy. The topic was Next In The Series. I'll give the questions here and pointers to the answers (actually the answers here and pointers to the questions since Jeopardy is an answer-and-question game.) Do you think some of these have non-unique solutions? If so, what are the other solutions? Are those problems unfair? As always I ask nonrhetorically. (my spell checker wanted me to put a space between non and rhetorically. I disagree.)

1. FA, SOL, ... NEXT
2. In the US Army: First Lt, Captain, ... NEXT
3. XXXVIII, XXXIX,... NEXT
4. FEDERAL HOLIDAYS: Memorial Day, Independence Day, ... NEXT
5. Orange, Yellow, (Wavelength around 510 nanometers)... NEXT

Knowing some History is a good thing- Why?

(FOCS registration is open: here. Note that there are tutorials on Sat Oct 22 and the conference talks are Sun Oct 23-Tues Oct 25.)

(Guest post by By Jeffery D. Stein, Chairman, IT History Society (info@ithistory.org), but first a related post by me.)

POST BY ME:

1. Often you find that the origin of your field is from a different field. Ramsey's paper where he proved (what is now called) Ramsey's theorem was actually a paper in logic, though he did say that his combinatorial lemma may be of independent interest. Knowing what he was working on expands your horizons.
2. If you study some history and then look around at the present world you will see some things in a different light. For example, if you study the history of Group Theory you realize that they didn't just write down some axioms and see where they led- they had actual applications in mind (e.g., showing the quintic had no solution in radicals). The axiomatic approach is fairly recent.
3. When teaching (say) cardinality it is good to know that this concept was once controversial and some mathematicians disagreed with it. Hence be patient with your students. I tell them that this concept was troubling and some of the controversy around it.
4. You can pick up some factoids of interest (and if you learn more about them they can become facts). I read an interview with Sheila Greibach (early Formal Lang Theorist) and, in passing, she mentions that any r.e. set can be written as the intersection of two context free languages. I never knew that! The other direction- the intersection of two context free Languages is an r.e. set is easy, but good to know for a HW or Exam question. (NOTE ADDED LATER- a commenter pointed out, correctly, that this cannot be correct. I will check what she actually wrote later.)
5. The items above are actually about the history of the IDEAS and not the people. Knowing something about the people can be interesting, but is likely less useful for research and teaching. If you disagree I would love to hear a respectful counterargument.

SO, how can we LEARN history? Today's GUEST POST is about some resources for this for the history of IT.

GUEST POST: Introducing an IT Teaching and Research Resource

Guest Post by Jeffery D. Stein, Chairman, IT History Society (info@ithistory.org)

In 2007, the IT History Society was formed. The Society is dedicated to informing IT companies about the value in preserving their history, helping archivists to be more effective in their work in preserving IT history, and most importantly being a reference point for the many international places of computing history information.

The Society wants to assist educators, students of information technology, and researchers in learning more about the history and background of the information technology industry, an industry that has had a significant effect on mankind in the past seven decades. It has nearly 700 international institutional and individual members (no charge to be a member). Institutional members include IBM, HP, Intel, the Smithsonian Institution, Computer History Museum, Charles Babbage Institute, MIT, Caltech, Hans Nixdorf Museum, British Library, Stanford Silicon Valley Museum, Deutsches Museum, IEEE History Center, UK National Archive, Hagley Museum, and more. Individual members include historians, computer scientists, and people who have worked in the industry from various countries. Currently the Society has many online databases; but, two in particular may be of great value for teaching information technology and research:

1. IT Historical Resource Sites Database. over 400 and growing every day, sites that have historical information about the information industry.  This entire database is completely indexed and searchable, which can be a beneficial aid in targeted search and research.
2. IT Honor Roll is database of over 800 names and growing, discussing individuals who have made a noteworthy contribution to the information technology industry.

Other information technology resources from the IT History Society are:

1. Calender of upcoming IT Historical and Archival events
2. Research links and tools to aid in the preservation of IT history
3. Over 1,000 Technology Quotes
4. An active Blog with discussions about historical IT events and the people behind them
5. A Social Network of IT history professionals, archivists, and hobbyists.

The Society is also in the process of creating three more databases about: (1) All information technology companies both past and present (2) All information technology software created, both past and present (3) All information technology hardware created, both past and present

The Society feels that these valuable resources can be of great benefit to information technology professors, teachers, assistants, researchers, and students. All databases are works in progress and each database has links for the IT community to add and grow the entries of each database. The Society is a non-profit educational and research organization.  It does not charge for membership or the use of its information.  The IT community supports our operations through donations to our 501 (c) (3) non-profit foundation. Please visit this link for further information.

The Anti-Privacy Generation

A physicist I knew refused to fly on small commuter planes. He knew what could go wrong and he was sure they weren't safe. In fact flying even on small planes is statistically safer than driving a car.

I thought about this story while I was reading Blown to Bits by Hal Abelson, Ken Ledeen and Bill's advisor Harry Lewis. The book is all about how the information revolution has put all our personal stuff out there. Knowing how computers and the Internet work can make one paranoid about information and this is why privacy is always a big issue among computer scientists and tech workers. But then I finally gave up on the book when I realized they gave very few examples of people who actually came to any harm from losing their privacy.

I've seen many a crypto talk talk about a situation where someone's personal information comes back to haunt them when they run for public office. But we live in a society that values openness. Obama didn't hide his illegal drug use, he talked about it in his autobiography and it didn't hurt his campaign. Anthony Weiner resigned from Congress not because he tweeted an inappropriate picture, but because he lied about it. Bill Clinton was impeached and Nixon resigned not for their actions but for their coverups.

Being open has its positive effects, it allows search engines, recommender systems and even people to tailor their behavior to your needs. We can imagine easily, as computer scientists, scenarios where loss of privacy has disastrous effects.  But your chances of running into such problems are about as high as being in a plane crash.

Do we use Technology before its perfected? Should we?

During Hurricane Irene I lost power for about 18 hours. I was actually pleased how short this was. PEPCO (my power company) did not tell us when power would be restored at any point. Why? Possibly because of this story that happened a few years ago.

On July 25, 2009 there was a power outage. I called PEPCO and was told

Your power will be restored by Sept 17 7:00AM.

I was glad to hear that since Sept 17 I was having company over at 7:00PM so I would have 12 hours to clean up and make dinner. PEPCO later had a spokesman that explained why they claimed it would take about 2 months to get my power back.. What they said (in our terms) is that they have a formula for how long it will take based on how many people lost power. The formula is (I am guessing) something like

Number of days = (number of people out of power)/1000.

This was a massive power outage- around 300,000 lost power. For those values the formula (we hope) is not correct. Power was restored to the entire region in about 5 days.

We are still learning how to automate things and sometimes we get absurd results. In a prior post I noted that a phone number gave automated info that was 2 years out of date. I've called airports at 2:00PM to find out when my lost luggage would be returned and found out that it will returned by 11:00AM (the same day three hours earlier).

I AM NOT complaining about PEPCO (I got my power back), The Airport (I got my luggage), or The Hallmark Channel (I missed a TV show I wanted to watch- not important). I AM raising an issue: Do we use technology before its perfected? Sometimes YES. Is this a bad thing? Is this a better way to beta-test things? Not sure- some errors only come up in extreme cases that were not thought about in the testing phase. The particulars of my examples are not important- is this a general problem? All of my examples are American- how is it in other countries?

Patrick Fischer (1935-2011)

Patrick Fischer, founder of STOC and SIGACT, passed away Friday at the age of 75. Fischer's research spanned from studying the relative power of different machine models in the early days of theoretical computer science to database theory later in his career.

In the late 1960's Fischer, realizing the growth of theoretical computer science, established the ACM Special Interest Committee on Automata Theory and Computability (SIGACT, now the Special Interest Group on Algorithms and Computation Theory) and served as its first chair. Fischer also served as conference chair for the first five Symposia on the Theory of Computing (STOC).

Fischer taught at Harvard, Cornell, Waterloo, Penn State and Vanderbilt.  In 1982, he was a target of the Unabomber. Fischer was away at the time but his secretary was seriously injured.

Fischer leaves behind his wife, Charlotte Froese Fischer, and brother Michael Fischer, both famous computer scientists in their own right. He also leaves a daughter Carolyn. A full obituary can be found here.

Update 8/31: New York Times Obituary

The Not-So-Simple Path

This post was inspired by the simple functions discussion on Bill's post and this question on unique paths.

A path is just a way from getting from point A to point B. A simple path is a path that doesn't cross itself. Some people use "path" to mean simple path and "walk" to mean a general path (like in random walk) but lets not quibble on notation.

To find a path you just keep going until you get there. To follow a simple path you need bread crumbs, some way of remembering where you've been. Often it doesn't matter. There is a path from A to B if and only if there is a simple path. The shortest path from A to B on a graph of positive edge weights is always simple. Ah but it isn't always so simple.

The randomized and deterministic log-space algorithms for undirected connectivity don't give anything close to a simple path. Counting the number of paths is easy, just take powers of the adjacency matrix. Counting the number of simple paths is #P-complete. The longest path is either infinite or easy to find. The longest simple path (Hamiltonian path) is NP-complete. Playing Go with players requiring to follow a simple path (no repeating a board position) is EXP-complete despite being played on a poly-size board. Making paths simple make them much more complex.

In our lives we need the ability to go back, to learn from our mistakes and try other possibilities. There is no where you can go without following a simple path but to follow one requires omniscience and trying to stay on a simple path will limit your choices. Life is not a simple path.

What inspired you to work on... whatever you work on?

Grad students often wonder how people get ideas of things to work on. The usual advice I give is (1) go to talks, (2) read papers, (3) talk to people, (4) follow through on all of the above. That's fine advice as far as it goes; however, I ask my readers to give examples, and I do the same.

Here are examples of how I found things to work on.

1. In ninth grade when I first heard that the fifth degree equation was not solvable I thought I really want to learn why that is true. I went to college and majored in math to find out. I arranged my courses to take Abstract Algebra as soon as possible and did find out and was happy. I could have dropped out right then; however, I heard that there were problems that could not be solved at all so I decided to stick around and learn about those.
2. As an undergrad at SUNY Stonybrook, in a combinatorics class taught by Joel Spencer, he said Infinite combinatorics is easier than finite combinatorics because all of those messy constants go away. This later inspired me to look at Bounded Queries in Recursion Theory. The reasoning was that P vs NP is hard, but maybe an infinite version of it would be easier. And in recursion theory you don't have time or space so I looked at number-of-queries as a complexity measure. I got out several papers and a book in this area; however, I never did solve P vs NP. Oh well. (Michael Sipser had far more mature thoughts along the lines of trying to solve an infinitary version of P vs NP. Some of that lead to Furst-Saxe-Sipser paper on parity not in constant depth poly number of gates.)
3. In grad school I read up on oracles that made P=NP and that made P ≠ NP. I wondered about other classes. Nobody had looked at oracles for NP vs DTIME(2^n). So I worked on that.
4. In grad school I saw Anil Nerode give a a GREAT talk on Recursive Mathematics. I was particularly impressed that we could take some of the objections of the constructivists and the Intuitionists and turn them into well defined math problems. Rather than say This proof is nonconstructive hence its BAD we now say This proof is nonconstructive, can I prove that it has to be so? How nonconstructive is it? Can some variant of it be constructive? This inspired me to work on recursive combinatorics. Right after the talk I marched to the Library and read two papers on Recursive Graph Theory.
5. In grad school I saw the Chandra-Furst-Lipton paper on Multiparty Communication Complexity at STOC. It really intrigued me that there was a matching upper and lower bound that was based on a combinatorial quantity that was not known. This talk got me interested in BOTH Ramsey Theory and Communication complexity!
6. When I got to UMCP in 1985 Carl Smith was working on Inductive Inference. At the time the field did not use much recursion theory beyond the recursion theorem and its variants. Carl knew the field, I knew recursion theory , so we collaborated.
7. I saw Dan Ullman give a talk on Richman games which inspired me to use Games as a way to motivate math and a good topic for high school and college projects.
8. At STOC 2000 I saw a talk on PIR's. I was intrigued by the model and read up on the area.
9. I reviewed Communication Complexity by Kushilevitz and Nisan which inspired me to work in that area.
10. In 2002 (or so) Jacob Fox (now a professor at MIT working on Combinatorics) emailed me asking about applications of Ramsey Theory. This inspired me to make a website of applications of Ramsey Theory. This forced me to learn some new ones. (I still maintain the website but its getting harder to do so since Ramsey Theory has gotten to be a standard tool that people use without much commentary.)
11. I read about the Polynomial Van der Warden Theorem, and that it had an elementary proof, on the web. I immediately tracked it down and read it.
12. Because I maintain the Applications of Ramsey Theory website Jon Katz emailed me a paper that applied Ramsey Theory to Proving that Programs Terminate. At RATLOCC I had heard about the reverse mathematics of the transitive Ramsey Theorem. I wrote an expository article on this application of Ramsey Theory but was also able to add some commentary from what I learned at RATLOCC (and by being in email contact with both the Applications people and the transitive Ramsey People.) NOTE- Once people know that you are interested in XXX they will send you articles on XXX to help you further the interest.
13. (A non-math example) There was an episode of Babylon 5 with the title A tragedy of telepaths. The authors intent was that this term be like A cast of hawks or A pretension of professors or A wedge of swans. I became fascinated with the question: are these really phrases? They ONLY appear in lists of such words. The phrase a tragedy of telepaths isn't even used in the episode! This inspired me to study the (ill defined) question When is a phrase a phrase? Now whenever I hear a new (to me) word or phrase that intrigues me, I type it into a file (which in LaTeX in alphabetical order), do a Google Search on it, and type in some commentary on its usage. I DO NOT look at word lists- this is a purely personal project.
14. In Kindergarten the teacher had a PhD in combinatorics (the job market was tough). Once when we were being bad she made us sit at our desks and Color the numbers {1,...,9} with RED and BLUE such that there is no three numbers equally spaced that are the same color. I was not able to do this (in fact, it can't be done) but I found the problem very interesting. Some other kid did manage to do it by using RED and BLUE on the same number to get PURPLE. The teacher asked that kid to try to do it for {1,...,27}. He cried. (I didn't remember any of this until much later when I learned VDW's theorem.)
15. Help me on my phrase list: Is there a term for a Math Phd in Combinatorics who is teaching Kindergarten and inspires one of her students to study Ramsey Theory?

The Future of Universities

When AT&T had its monopoly, it could afford Bell Labs, a major research institution that bragged at having more Ph.D.s than any other university. Now very few companies have basic research labs.

The newspaper industry had a high cost of entry. It required a large number of resources from reporters to presses to create a paper that could challenge existing publications. Established newspapers had a high profit margin and could afford a separate mission, to have a news department with high journalistic standards acting independently from the business side of the paper. The Internet effectively eliminated that high cost of entry and great journalism gets harder to find.

Universities, mostly non-profits, have both an education and research mission. Universities get the bulk of their revenue from student tuition and donations from former students. Universities also have a high cost of entry and we have seen very few new major universities, particularly in the US, established since 1900. Universities, while they can't turn a profit, have the freedom to have strong researchers and research facilities.

The Internet, combined with AI and social networks for support and grading, will allow a course to reach a huge number of students. Witness the Stanford AI course with over 85K registered students and the press it has received. The technology isn't quite there yet, but in ten years or so it will be easy to scale up courses with little scaling in personnel. Why would anyone take courses from me when they could get a superior experience from Scott or Luca? How long before a virtual Internet university can provide a better education than any single physical school?

The top universities will likely survive but what will happen to the mid-level schools still stocked with excellent scientists? If fewer universities fund basic research then who will?

An application of Ramsey Theory to Proving Programs Terminate

B. Cook, Podelski, and Rybalchenko have done both practical and theoretical work on proving that programs terminate. They use Ramsey's Theorem (Yeah!). Jon Katz send me their paper. After some emails with them and others I wrote an exposition. Their papers are here (I used Transition Invariants (LICS 2004) and Proving Program Termination (CACM 2011), though there are others on that page that are relevant.) My exposition is here. This post will briefly describe what they do. For more detail see either their papers or my exposition.

If w is a variable in a program and A is a set then

w = input(A);

means that w gets SOME value in A, supplied by the user.

Consider the following program

w = input(N);
x = input(N);
y = input(N);
While w>0 and x>0 and y>0
        control = input(1,2)
        if control = 1 then
                x=input(x+1,x+2,...)
                y=input(y+1,y+2,...)
                w=w-1
        else
        if control = 2 then
                y=input(y+1,y+2,...)
                x=x-1

A Proof that the Program terminates that does NOT use Ramsey's Theorem

How would you prove that it terminates? One way is to (1) find a map f : NxNxN --> L where L is a well founded order, (2) show that in each iteration of the loop f(x,y,z) decreases, (3) show that if f(x,y,z) bottoms out then the program has halted (perhaps earlier than this point).

For this program the key is not the function f, which will just be f(w,x,y)=(w,x,y) but the ordering. We map to the ordering (N x N x N, <_lex). In every iteration either (1) w decreases, so (w,x,y) decreases even though x and y may get much larger, or (2) w stays the same and x decreases, so (w,x,y) decreases even though y may get much larger. Hence (w,x,y) decreases. Hence, eventually, one of the components is 0, and then the program halts.

A Proof that the Program Halts that Uses Ramsey's Theorem.

Assume, by way of contradiction, that there is a way the user could supply initial w,x,y and also controls in every iteration, so that the program runs forever. Let the infinite sequence of states of the program be:

(w1,x1,y1), (w2,x2,y2), ..., (wi,xi,yi),..., (wj,xj,yj), ...

Claim: Either w_i < w_j or x_i < x_j. If between steps i and j we ever have control=1 then w will decrease. If we only have control=2 then x will decrease.

We now color all (i,j) as follows: if w decreased then color it W, if w did not decrease but x did then color it X. By Ramsey's theorem there is a homogeneous subset.

i1 < i2 < i3 ...

If the color is W then we have

wi1 > wi2 > wi3 > ...

AH-HA- so w must eventually be 0 and the program terminates, contradiction. Similar for if the color is X.

What to make of all of this?

1. In the first proof we only had to prove things about ONE step of the program (YEAH!) but we had to deal with a complicated well founded ordering (BOO!).
2. In the Second proof we had to prove things about ANY sequence of steps of the program (BOO!) but only had to deal with a simple well founded ordering (YEAH).
3. There are examples in my exposition and in their papers where the Ramsey approach really does give an easier proof.
4. We didn't use the full strength of Ramsey's theorem (Henceforth RT). Note that the coloring is transitive: if i < j < k and (i,j) is RED and (j,k) is RED then (i,k) is RED. We used RT restricted to Transitive colorings. We call this the Transitive Ramsey Theorem or TRT. TRT for 2 colors is actually the Erdos-Szekeres theorem (See here for six or more proofs, article title Variations on the Monotone....) TRT for c colors is a natural (and easy) generalization of the Erdos-Szekeres theorem. (I included the proof of this in my exposition for completeness, however, if someone has a reference please leave a comment.)
5. Is RT actually stronger than TRT? There are three ways to ask this question, and in all three the answer is yes. See my exposition.

My Cruise Vacation

Last week, my wife and I took a vacation to the Caribbean on the biggest cruise ship there is. I like cruising, just relaxing, swimming, reading, eating, drinking and not having to think much. There is something cool to zip-lining, boogie boarding and ice skating on a cruise ship. Since, as most of you are thinking, no right-minded academic would ever be caught on a cruise ship, I had no chance of running into another computer scientist. So peaceful.

A cruise used to keep you isolated from the outside world. Not any more. This ship had WiFi and cell phone service throughout the ship. If I was willing to pay the costs, I'd be even more connected on the ship than at home. My wife insisted on getting the large WiFi package so she could check emails from her business. I avoided reading email but did check the news. Too bad as I found out that I lost much more money in the market than the cost of the cruise, we were only days ahead of a potential hurricane and the Yankees swept my White Sox. Better to have been isolated and blissfully happy in the great weather we did have.

Computers are taking over cruise ships in lots of ways. About half the people reading read on e-book readers, usually Kindles. The photo kiosks used facial-recognition software to figure out which photos are yours. We had a single card that served as a room key, tickets to the shows, charge card for drinks, and many other roles. One day my cell phone will do all this in real life. One day.

During a Q&A with the captain, he was asked what happens when someone falls overboard. He gave a surprisingly detailed answer: "Rarely does someone 'fall' overboard, they are either pushed or they jump. If we know about it right away, we have a procedure to stop the ship and have a special rescue boat and trained crew to search. If we don't know about it right away, we have cameras so we can determine when they fell and since we know where we were, we radio for a search boat. If it is a day later...I'd better stop there."

The next step would be to use computer vision techniques to automatically tell when someone "falls" off a boat, so there is no day later.

What is a simple function?

In my discrete Math course I asked the following question:

For each of the following sequences find a simple function a(n) such that the sequence is a(1), a(2), a(3),..

a) 10, -17, 24, -31, 38, -45, 52, ...

b) -1, 1, 5, 13, 29, 61, 125, ...

c) 6, 9, 14, 21, 30, 41, 54, ...

(For the answer see here)

Some students found this problem difficult. Looking back at it they may be right- the pattern is not obvious for students at that level who do not know what to look for. Some noted correctly that the term simple function was not defined in class. I meant a function that does not involving summations or recurrences, though I do not think that quite captures the notion. For example, if a student wrote a poly that interpolated the values given that is not that I wanted. I could ask for the function with the least Kolmogorov complexity to describe but that's not quite right for this sophomore class where they struggle to learn induction.

One of them, in earnest, emailed me this Wikipedia entry on simple functions which defines them as a linear combination of indicator functions of measurable sets. Hmmm- not quite what I had in mind for this class. The student wanted to know if he could use it. I told him no; however, in retrospect, I wonder what he would have come up with.

I had not known that the term simple function had a formal definition. Usually in a class there are concepts that are well enough defined within the class though not quite formal. With Wikipedia (and other web sources) it may be harder to have this kind of classroom-language since terms may have a formal definition that you didn't know.

If I was a tweeter (is that a word?)

Since Lance is not tweeting this week, I will take up the slack. So, here is my once-in-a-while post

If I tweeted AND if tweets didn't have to be so short, here is what I would tweet:

1. Possibly the youngest blogger: a 7-year old has a blog called Life Before The Dinosaurs. It's about... life before the dinosaurs. It's serious. It's not a stunt. His mom types it in for him.
2. More money in SOLVING problems then showing they are UNSOLVABLE:
   1. Decision Problem: Solvable cases of the Quantificational Formulas costs $80.00 used, on amazon.
   2. Decision Problem: Unsolvable cases of the Quantificational Formulas costs $9.00 used, on amazon.
3. Math on TV: On NCIS, the episode Red Cell McGee and Abby argue over whether the math they are looking at is homology or cohomology. I couldn't tell who was right.
4. Other blog (not this one of course) have a problem with nasty comments. Why? See here for a possibly explanation.
5. The new Minister at my church has a math degree. I'll ask him if Jesus used the Banach-Tarski Paradox to perform the the miracle of the five loaves and two fish.
6. A use of Banach-Tarski in Norse mythology: here.
7. A play with some math themes called Completeness. Sounds interesting but I'm not going to pay $70.00 to find out.
8. There were identical twins in my Discrete Math class. GREAT for You have n people. Two are identical twins that you cannot tell apart. How many different ways can they appear to line up? TERRIBLE for If I was to ask everyone in this room their birthday what is the probability that two of them have the same one?

Does STOC/FOCS take simple-nice-ideas papers? A one-element case study

WRITTEN AUG 1,2011: It has been said that simple innovative ideas to not get into STOC/FOCS and only hard technical improvements do. This is one of the motivations for the INNOVATIONS conference. But is it true? People mostly toss out anecdotal stories and, alas, I will do the same. But with one difference. The next few paragraphs were were written in September 2010, BEFORE the STOC decisions came out.

WRITTEN IN SEP 2010: Dave Mount gave a brilliant talk at today's internal UMCP theory day on a joint paper he wrote with Sunil Arya and Guilherme da Fonseca. I actually understood it! It is a perfect example of something that is so simple, clever, obvious-after-you-see-it, and useful that it might not get into STOC. Dave thought it would not get in for this reason. I am less sure. However, Dave Mount and I agree that when the decision is made I will blog about it. If the paper gets in it will be an anecdote that counters the only-complicated-papers-get-into-STOC notion. If the paper does not get in then it will be an anecdote that supports this notion. Either way I get a post out of it and Dave, Sunil, and Guilherme get publicity for their results (either in anger or in joy).

Here is the problem of interest and their variant on it.

1. Given a set S of n points in d-dim space create a data structure so that the question: given point q, find the point p in S that is closest to q. We want low space and quick time. This seems hard to achieve.
2. Given a set S of n points in d-dim space, and a parameter ε, create a data structure so that the question: given point q, find the point p in S that is at worst (1+ε)OPT away from q. This is called Approx Nearest Neighbor. We call it ANN.

Here is what was known: In Space-Time Tradeoffs for approximate nearest neighbor searching, by Arya, Malamatos, Mount, they showed a very complicated algorithm that did the following. View d as being constant. S is a set of n points in d-dim space. ε is also an input.

1. Let γ be a tradeoff parameter with 2 ≤ γ ≤ 1/ε. There is a data structure for ANN with
   1. space O(n γ^d-1log(1/ε)), and
   2. query time O(log(nγ) + 1/(ε γ)^(d-1)/2).
2. If γ=2 then space O(nlog(1/ε)) and query time O(log n + 1/ε^(d-1)/2).

The new result was an improvement and was easy to code and use. I won't state it since it is not easy to typeset (AH HA- maybe being hard to typeset will give them an edge) but here is the paper: Approximate Polytope Membership Queries, (CONFESSION: that very last link was revised in July 2011, but the rest was written in SEPT 2010.)

WRITTEN IN FEB 2011: CONGRATS to Dave, Sunil, and Guil. Their paper got in. That's one anecdote against the notion that STOC does not nice simple ideas. If YOU (the reader) have some other ones, please leave them as comments.

WRITTEN IN JUNE 2011: The STOC talk was EXCELLENT. Here are the slides.

The Problems of LaTeX

By request a post that may create the biggest backlash since I declared myself Unix free.

\begin{rant}
LaTeX is a great system for mathematical documents...for the 1980s. But the computing world changed dramatically and LaTeX didn't keep up. Unlike Unix I can't give it up. I write papers with other computer scientists and mathematicians and since they use LaTeX so do I. LaTeX still has the best mathematics formulas but in almost every other aspect it lags behind modern document systems.

WSYWIG: I love seeing the final document as I write it. There are front ends to LaTeX that approximate this but they produce LaTeX code that make it near impossible to collaborate unless everyone uses the same editor and we don't. "Code" is the right word, I have to compile a LaTeX document then start a separate program to see it.

Collaboration: The very reason I'm stuck with LaTeX is its greatest weakness. We all have different macros, style files and bibtex formats (and some don't use bibtex at all). We all have to agree in the beginning which of our homegrown stuff we want to use and merging already written documents is a bear. How often does some one send you a LaTeX document and you have to email back that they forgot some style file?

LaTeX documents are saved as text files which have different formats on different machines. I hate seeing ^M at the end of every line. Some people to break up LaTeX lines at reasonable places, other people don't messing up my editor and trying to figure out what my co-author has changed.. At least email attachments avoid the old ¿From problem.

Microsoft Word has a great system for tracking revisions. Google Docs lets people edit at the same time. Nothing close to either for LaTeX.

User Friendly: LaTeX is not user friendly. Try opening a text editor and (without looking at an old LaTeX document) write a LaTeX document to say "Hello World!" that will compile on the first try. Now go to Google Docs, create a new document and type "Hello World!". See the difference. Don't even get me started on creating a table.

Backward Compatibility: In the early 90's, LaTeX went through a major upgrade. There was a compatibility mode that claimed to be fully backward compatible. Not even close. Then they changed the font system, rendering my old documents unreadable. Luckily LaTeX hasn't changed significantly since then.

It's not difficult to convert between Word, Docs and most other document systems but nearly impossible to move to/from LaTeX.

I don't use LaTeX when I don't need to. I usually use Word or Docs for recommendation letters and other documents without much formulas and references including my upcoming P/NP book.

What we need is a way out of LaTeX, add-ons to Google Doc that make it as nice for math as LaTeX, and the ability to import old LaTeX documents, style files and bibtex files. Not holding my breath.
\end{rant}

Why did 1+1=2 take Russell and Whitehead 300 pages?

In my post about the myth that Logicians are crazy I mentioned in passing that Whitehead and Russell spend 300 pages proving 1+1=2 (but were both sane). Two people privately emailed me:

Are you sure Russell and Whitehead weren't a few axioms short of a complete set? How could they take 300 pages to prove 1+1=2. Isn't it... to obvious to be worth proving?

I responded by saying that they had to define 1, +, =, and 2 rigorously. One of them responded Are you a few limit points short of Banach space? That aside, there are some questions the 1+1=2 proof brings up:

1. How did they spend 300 pages proving 1+1=2?
2. Is it easier in ZFC?
3. How important is or was Principia Mathematica? Wikipedia says PM is widely considered by specialists in the subject to be one of the most important and seminal works in mathematical logic and philosophy since Aristotle's Organon. The Modern Library places it 23rd in a list of the top 100 English-Language nonfiction books of the twentieth century. Here is the list they are referring to. The other books look... readable.
4. I had thought that nobody reads PM anymore; however, its entry on amazon says it has a rank of roughly 294,000. This is far better than a book that truly nobody reads. For example this book has an Amazon rank roughly 5,300,000.
5. While more people are buying it than I thought, are people actually reading it? Did they ever? My guess is no and no, but I really don't know.
6. Can a book be influential if few people read it? Yes if they are the right people. Godel read it and I think it inspired him. (Its mentioned in the title of his Incompleteness paper.)
7. PM was an early attempt to formalize all of math from the ground up. This may be one of those tasks that you are almost destined to do in a clunky way before doing it smoothly.
8. I am talking in a vacuum here, having never read it. If any of my readers have actually read it and want to comment on what it was really like, you are more than invited to do so.

Delay for a Postdoc

Suppose you have a tenure track offer at the University of Southern North Dakota and a postdoc offer at MIT. Tenure track jobs are hard to get so you want to accept the USND position but before you spend your life in Hoople you'd like some more time in a top research place.

So you ask the CS chair at USND if you can spend the next year as a MIT postdoc before going to USND. The chair needs you to teach algorithms that spring. Also if you don't take the job, he may lose the position to the music department. What are his choices?

1. Say no, that you have to start this fall or not come at all. This runs the risk that you will not accept the USND position.
2. Say yes and find someone else to cover algorithms. This has a different risk, that you might find some other job and not come to USND at all.

Is it ethical for you to say you are coming to USND in a year and send out new applications in the fall? What if you don't go outright looking for a job but Michigan asks you to apply? Is it ethical for Michigan to pursue you if it knows about your promise to USND? What if you fall in love with someone in Ann Arbor?

Someone I know (not CS) turned down an academic job she had promised to take. The school sent her a bill for $12,000 to cover the expenses of finding someone else to cover the classes. She didn't pay.

One economic solution: The chair agrees to the postdoc but requires you to pony up $12,000 now which you will get with interest when you start at USND. Trouble is most grad students don't have $12,000 to pony up and probably would walk away from a school making this offer.

This would be much easier if universities worked like baseball teams. In order to get you, Michigan could offer USND Seth Pettie and a grad student to be named later.

Looking for people to review books for my column

I am looking for reviewers for the following books for my SIGACT NEWS book review column. I will try to edit this post to keep the list up to date; however, if you are reading this past July 28 then you should look at the this list which I am constantly updating.

1. Look here for advice for reviewers.
2. Look here the LaTeX template.
3. Look here for past columns.

IF you want to review a book then FIRST goto the advice for reviewers and see if you really want to review a book. If so then email me your name and postal address to send the book (if you are out of the country I will have the publisher send it to you). Your reward for doing the book review: a free copy of the book! I would like to get requests before July 28 since that is when the next column goes to press and I would like to have an updated books list there; however, if you ask me past that date, and the book is still available, you can still review it. (ADDED LATER- DEADLINE IS MID-OCT OR MID-NOV, BUT CAN BE NEGOIATED IF THERE IS A REASON FOR LATER.)

Bio Comp

1. Introduction to Bio-ontologies by Robinson and Bauer.

Math

1. The Dots and Boxes Game: Sophisticated Child's play by Berlekamp.
2. New Mathematical Diversions by Martin Gardner.
3. The Magic Numbers of the Professor by O'Shea and Dudley.

Books on Misc-Comp Sci

1. Random walks and diffusion on graphs and database by Blanchard and Volcanic.

Disproving the Myth that many early logicians were a few axioms short of a complete set

While I was working on this post another blogger posted on the same topic here and I found a book review of Logicomix that touched on some of the same issues here. (For MY review of Logicomix see here.) They are very good sources and I will refer to them in this post.

There is a notion that logicians who work in foundations early on in the field were crazy. I give examples of where this is said and then I look at the real evidence.

1. In Rudy Rucker's post about Turing he writes

   ... it really does seem possible that Turing killed himself. Like the other logicians Godel and Cantor, he seems to have been somewhat nuts. Funny how many logicians are crazy and irrational. A paradox.

2. In Logicomix, a great comic book about the foundations of logic, there is an allusion to Logicians being crazy.
3. In Gian-Carlo Rota Indiscrete Thoughts he writes: it cannot be a complete coincidence that several outstanding logicians of the 20th century found shelter in asylums at some point in their lives: Cantor, Zermelo, Godel, and Post are some.

I've also seen an explanation for this alleged phenomena: Logicians were searching for absolute certainly and either it can drive you crazy or thinking you can find absolute certainly means you were crazy ahead of time.

So the people above, and others, give some examples of logicians being crazy and then claim that many logicians are crazy. I am reminded of people who say It was cold the other day, looks like Global warming is wrong.

Let us look at the actual record. I will look at all of the logicians in Wikipedia's list of logicians who

1. were born between 1845 and 1912. (1845 is when Cantor was born, 1912 is when Turing was born.)
2. I ruled out a few people who were really philosophers, and also Banach who I don't think would call himself a logician.

For each logician on the list who meets my criteria I say if I think they are sane or a few axioms short of a complete set. I am not a historian--- corrections are more than welcome. I also freely admit that crazy is not well defined.

You may well disagree with what years I pick and my opinions. The point is to get an intelligent discussion going.

1. Wilhelm Ackerman (1896-1962): He defined the function that bares his name. He also worked on the epsilon-calculus which formed the basis for Bourbaki's logic. Reading Bourbaki might drive one crazy; however, forming the basis for it does not. He was quite sane (Ackerman that is-- Bourbaki had multiple personality disorder.)
2. Alice Ambrose (1906-2001): She had the longest lifespan of anyone on this list. She studied with Moore and Wittgenstein and got two PhD's. (In those days a women had to do twice as much as a man to get a job.) She was more on the philosophy side of logic, but certainly had math training. She wrote a textbook with her husband, known as Ambrose and Lazerowitz. Sane!
3. Paul Bernays (1888-1977): He worked with Hilbert on alternative set theories. Sane!
4. Evert Willem Beth (1908-1964): He helped to establish Logic as a discipline. Sane!
5. L.E.J. Brouwer (1881-1966): He thought that all math should be constructive. This point of view lost the battle if ideas; however, that does not make him crazy. The Wikipedia article quotes Martin Davis as saying: he felt more and more isolated, and spend his last years under the spell of totally unfounded financial worries and a paranoid fear of bankruptcy, persecution, and illness. However, Dirk van Dal en wrote a scholarly two-volume biography of Brouwer that indicates that Brouwer was not crazy. And I agree. Sane!
6. Georg Cantor (1845-1918): He had a new way of looking at infinity that was brilliant and is now accepted. That does not make him crazy. He was also convinced that Bacon wrote the plays of Shakespeare and that Joseph of Arimathea was the father of Jesus Christ. That does not make him crazy. However, he was obsessed with these views and was in and out of sanitariums. A few axioms short of a complete set.
7. Rudolph Carnap (1891-1970): I originally thought he was more of a philosopher; however, he published in thermodynamics and the foundations of probability. He fled Hitler's regime and later refused to sign a loyalty oath in America (during the McCarthy Era). His second wife committed suicide. He led an interesting life but was sane.
8. Alonzo Church (1903-1995): He invented (discovered?) The Lambda Calculus, proved that Peano Arithmetic was undecidable, and articulated what is now called the Church-Turing Thesis. These are all sane things to do. (Bob Soare distinguishes Church's Thesis from Turing's Thesis here.)
9. Haskell Curry (1900-1982): He worked in combinatory logic. There is a programming logic named after his first name! (see here). Sane!
10. Adolf Fraenkel (1891-1965): The F in ZF-set-theory. Provably Sane!
11. Gottlob Frege (1848-1925) He hated Jews, Catholics, and the French. That might make him unpleasant to hang around, especially if you are a French Jew who converts to Catholicism. However, that does not make him crazy. He is often given as an example of someone who was crazy, though the links ( here and here) argues for Frege being sane. I defer to the two links. Sane!
12. Gerhard Gentzen (1909-1945): He made the cut- Sane!
13. Kurt Godel (1906-1978): He stopped eating because he thought people were trying to poison his food. They weren't. A few axioms short of a complete set.
14. Jean Van Heijenoort (1912-1986): Best known in Logic for writing From Frege to Godel, a history of Logic from ... Frege to Godel (duh). Best known outside of logic for being Trotsky's secretary and later a historian of that movement. He was killed by his estranged fourth spouse. An interesting life, an interesting death, but he was sane.
15. Jacques Herbrand (1908-1931) Has the shortest lifespan (died at 23 in a mountaineering accident) of anyone on this list. He worked in proof theory. Sane!
16. Arend Heyting (1898-1980) He continued Brouwer's work on intuitionism. Sane!
17. David Hilbert (1862-1943): In Logiccomix they claim that Hilbert's son Franz had a mental illness and Hilbert cut off all contact with him. However, this refutes this and claims that Hilbert's son was only put away for 3 years and then re-joined his family. One may question if David Hilbert deserves a World's Greatest Father mug, but one cannot question his sanity.
18. Clarence Irving (1883-1964): He took exception to Principia's use of material implication. I'm impressed that he read and understood Principia enough to have objections. Sane!
19. Stanislaw Jaskowski (1906-1965): He worked in Intuitionistic Logics. Since I can't prove that he was crazy I assume he was sane.
20. William Ernest Johnson (1858-1931): He wrote three volumes on logic which showed technical expertise but was superseded by Principia Mathematica. This did NOT drive him crazy. Sane!
21. Philip Jourdain (1879-1919): He was interested in paradoxes and formed the card version of the liar's paradox. He also worked on algebraic logic. Quite sane. His sister Eleanor Jourdain claimed to have traveled through time and seen ghosts, but was not a logician.
22. Stephen Kleene (1909-1994): Kleene hierarchy, Kleene star, Kleene algebras are all named after him. He also proved the recursion theorem. Did this go to his head and make him insane? NO- he was totally sane.
23. Christine Ladd-Franklin (1847-1930): Her PhD was on Algebra and Logic. She faced problems being a women in a man's field but kept her sanity.
24. Stanislaw Lesniewski (1886-1939): He rejected axiomatic set theory (because of Russell's paradox) and tried to obtain other formal systems to replace it. A noble effort that failed. Still, he kept his sanity.
25. Adolf Lindenbaum (1904-1941): He proved Lindenbaum's Lemma- every consistent theory of predicate logic can be extended to a complete consistent theory. Like many major advances, profound at the time, easy to prove now. Certainly sane.
26. Leopold Lowenheim (1878-1957): The Lowenheim of Lowenheim-Skolem. See Skolem for more on that. A model of sanity.
27. Jan Lukasiewicz (1978-1956) Wikipedia says He thought innovatively about traditional propositional logic. Is innovatively a word? My spell checker does not think so but whoever wrote his Wikipedia entry thinks so. Sane.
28. Saunders Mac Lane (1909-2005) (He preferred the space between Mac and Lane.) His PhD thesis was on Logic and he also worked in Category theory. But he also did lots of Algebra. Sane.
29. Carew Arthur Meredith (1904-1976): He worked on obtaining short axiom basis for logic systems. Sane.
30. John von Neumann (1903-1957): Calling him a logician seems odd since he contributed to so many fields. Sane.
31. Jean Nicod (1893-1924): Co-discovered the Sheffer Stroke from which you can do everything in prop logic. Sane.
32. Pyotr Novikov (1901-1975): He proved the word problem for groups undecidable. His son Sergei Novikov won a Fields Medal in 1970 and, more importantly, is a professor at The University of Maryland! Sane.
33. Giuseppe Peano (1858-1932): His Wikipedia entry calls him the founder of Mathematical Logic and Set Theory. That seems over-the-top, but not by much. His axiom system is still the standard. Sane.
34. Emil Post (1897-1954) He introduced Turing Degrees. In the mid 1940's he posed Post's Problem which is to find a r.e. set (now called c.e.) that is neither decidable nor complete. This was solved in 1956 by Friedberg and Munhnik independently. He suffered from mental illness. A few axioms short of a complete set.
35. Mojzesz Presburger (1904-1943): Presburger proved Presburger Arithmetic was decidable. What are the odds of that!? Sane!
36. William Quine (1908-2000): He was more of a philosopher; however he did do some math. At Harvard he taught Symbolic Logic every fall for 50 years. That might drive some crazy; however, he was quite sane.
37. Frank Ramsey (1903-1930): The paper where he proved what is now known as Ramsey Theory was titled A Problem in Formal Logic and solved a case of the Decision Problem. He regarded himself as a logician so we shall too. Speculation: He would be surprised at where his work lead to (combinatorics) and then pleased that it lead back to logic again : The Large Ramsey Theorem (see also here) and much work in the reverse mathematics of Ramsey's theorem".
38. Raphael Robinson (1911-1995): He worked in Logic and Number Theory. He is probably best known for his work on tiling the plane. He married Julia Bowman (who changed her name to Julia Robinson) who was also a logician but born in 1919--- a little too late to be on this list. Having two academics in the same area get married might drive some crazy, but not them. Sane!
39. J. Barkley Rosser (1907-1989): He strengthened Godel's incompleteness theorem. Sane!
40. Bertrand Russell (1872-1970): He was obsessed with the quest for certainty; however, that does not make him crazy. He had several wives (not at the same time) and believed in open marriage. He was not crazy, just ahead of his time. Sane.
41. Moses Schonfinkel (1889-1942): He worked in Combinatory Logic. By 1927 he was in a sanitarium. The only non-famous logician on my list who was a few axioms short of a complete set.
42. Thoralf Skolem (1887-1963): He is best known for the Lowenheim-Skolem theorem: The notion that any consistent set of axioms has a countable model is very interesting--- One corollary: there is a countable model of the reals. Thinking about that might drive some crazy, but not him. Sane!
43. Alfred Tarski (1901-1983): The Banach-Tarski paradox is crazy; however, Tarski was not. Sane.
44. Alan Turing (1912-1954): He defined Turing Machines, though he didn't call them that. The story I had assumed was true is that the British Government made him take hormones (or something) to cure him of his homosexuality, and this drove him to suicide. But the story doesn't quite work with the timeline. He committed suicide a few years after he was forced to take drugs. Delayed reaction? Suicide for some other reason? Really was an accident? In any case, since his possible suicide is the only evidence that he was crazy I say Sane!
45. Nicolai Vasilev (1880-1940): The originator of non-Aristotelian logics. Sane.
46. Alfred North Whitehead (1861-1947): In Russell-Whitehead's Principia Mathematica they spend 300 pages proving that 1+1=2. This might drive some insane but not him. Whitehead was stark raving sane.
47. Ludwig Wittgenstein (1889-1951): He gave away all his money and seemed to be a self-hating Jew. Odd yes, but he was sane. (NOTE- Scott Aaronson left a comment that argues that Wittgenstein should be classified as a few axioms short of a complete set. I believe his arguments (they are backed up by facts) and may later redo the stats at the end of this post.)
48. Ernest Zermelo (1871-1953): The Z in ZF set theory. He disapproved of Hitler's Regime. Hardly crazy. Rota says that Zermelo was crazy but neither I nor this post have been able to find any evidence of this. Zermelo did spend time in a hospital for lung problems, which may have confused Rota.

So what to make of all of this?

1. Cantor, Godel, Post and Schonfinkel were crazy. So we have 4 out of 48 were crazy. That's around 8%. This website claims that 6% of all people are crazy. So 8 seems high, but the sample space is pretty small. Conclusion: Same as the posts on the same topic referenced at the beginning: the notion that people in logic are crazy is not well founded. In addition, this post argues that the problems Cantor, Godel, and Post had were unrelated to their study of logic. (There was no comment on Schonfinkel.)
2. AH- but Rota said that so many outstanding logicians were crazy. Since three of the four who I say were crazy were outstanding there may be a point here. One could look at who on my list was outstanding and see what percent of them logicians were crazy. However, determining who was outstanding is even harder than determining who was crazy, so I leave it to others to continue this work.
3. There were some on the list that in my opinion were sane but others think were crazy: Brouwer, Frege, Turing, Zermelo. Perhaps more. If enough of them turn out to be crazy then there may be something to this logicians are crazy theme; however, I doubt this will happen.
4. Was it crazy to spend so much time and effort on this one post? I am not on the logic list, nor was I born between 1845 and 1912 so the answer is not relevant to the study.
5. This blog posting has a crazy number of links: 71. That breaks the record for this blog which was held by this entry which had around 37.

Math, the Universe, and Everything: Max Tegmark's Interpretation of reality (guest post)

(This is a guest post by Nadia Jones who blogs at online college about education, college, student, teacher, money saving, movie related topics. You can reach her at nadia.jones5@gmail.com. Why is she doing a guest blog? She asked me, pointed me to some of her work, and suggested some topics that seemed reasoanble. You can do that too!.)

Math, the Universe, and Everything: Max Tegmark's Interpretation of Reality

Despite how much mathematicians like to think that their work is the end-all, be-all, it can be sometimes quite complicated to explain to friends and family who are not familiar with the pleasures and perils of doing high-level math exactly why it is so important. At the same time, however, devout followers of math still realize that there is an element of get-your-head-out-of-the-clouds, especially when dealing with abstract mathematics that do not directly apply to career paths that are lucrative or have potential for advancing research in an academic setting.

But what if someone were to tell you that everything that we know, everything that we feel, is all a complex series of mathematical structures? Of course, many have theorized that math and disciplines that are heavily math-based like physics, are very accurate ways to describe the world as it exists, but cosmologist Max Tegmark takes things one step further.

In an absolutely fascinating article published in Discover Magazine, here Tegmark explains his theories that were almost impossible to publish or even be taken seriously a few years ago. Taking a leaf out of string theory's book, Tegmark has endeavored to explain what is known in popular science as "alternative" or "parallel" universes. In more serious academic circles, these universes are known as "multiverses." Tegmark notes that others have posited three multiverses, but he has added a fourthâthe mathematical multiverse. (Another article about Tegmark is here.)

Tegmark describes this particular multiverse as such in the Discover interview:

Galileo and Wigner and lots of other scientists would argue that abstract mathematics describes reality. Plato would say that mathematics exists somewhere out there as an ideal reality. I am working in between. I have this sort of crazy-sounding idea that the reason why mathematics is so effective at describing reality is that it is reality. That is the mathematical universe hypothesis: Mathematical things actually exist, and they are actually physical reality.

Although Tegmark's work has not received as much critical attention as other mathematician's work, it his is melding of physics, pure math, and cosmology that has helped his research be more seriously considered. For more information on Tegmark's theories, check out his MIT hosted website, The Universes of Max Tegmark

A slightly diff take on Lipton's use of Ramsey's Theorem

This post takes an idea of Dick Lipton's in a slightly different direction.

ω(G) is the size of max clique in G.

Recall that, for all 0 < δ₁ < δ₂ < 1, the following problem is NP-hard: Given a graph G with the PROMISE that either ω(G) ≤ n^δ₁ OR ω(G) ≥ n^δ₂, determine which one it is. Output NO in the first case and YES in the second case. (Reference: David Zuckerman proved the result here by derandomizing a result of Johan Hastad that had as its conclusion ZPP=NP rather than P=NP. See here for Hastad paper.)

Note the following,

If ω(G) ≥ n^δ₂ then, by Ramsey's Theorem and the current bounds known on the Ramsey numbers, for ANY 2-coloring of the edges of G there will be a mono clique of size (0.5)*(δ₂)log n. (Slightly larger values can also be obtained.)

This gives rise to the following POSSIBLE RTIME(n^{O(log n)}) algorithm for the promise problem.

1. Input G
2. Do the following n^{Alog n} times Or until you get a NO. (A is a constant that we pick later.)
   1. Randomly 2-color the edges of G
   2. Look for a mono clique of size (0.5)*(δ₂)log n. (This takes n^{O(log n)} time.)
   3. If you DO NOT find one then output NO and stop. (In this case you KNOW the answer is NO.)
   4. Otherwise try again.
3. (If you got here then every coloring you tried had a mono clique of size (0.5)*(δ₂)log n.) Output YES. (You are NOT SURE that this is correct.)

The algorithm clearly runs in time n^{O(log n)}. But does it work? And what should A be?

1. IF ω(G) ≥ n^δ₂ then the algorithm will correctly say YES.
2. IF ω(G) ≤ n^δ₁ then will the algorithm find a coloring that shows this? Or more precisely, will this happen with high prob?

In order to get NP in RTIME(n^{O(log n)}) we need the algorithm to work for SOME 0 < δ₁ < δ₂ < 1. Hence we need the following CONJECTURE to be true:

There exists 0 < δ₁ < δ₂ < 1, A, and a function p(n) = n^{Alog n} such that the following is true: For almost all graphs G with ω(G) ≤ n^δ₁ the prob that a rand 2-coloring of the edges will have a mono clique of size (0.5)*(δ₂)log n is LESS THAN (1-p(n)). (ADDED LATER: Almost All Graphs means for all but a FINITE number of graphs.)

So, what to make of this?

1. One MAY think the following; Since we DO NOT think that NP is in RTIME(n^{O(log n)}) the conjecture is false. Perhaps it can be PROVEN false (unconditionally) using the techniques of Zuckerman or Hastad, or other techniques in the area.
2. Is our confidence that NP is not in RTIME(n^{O(log n)}) SO STRONG? We could at least TRY to prove the conjecture.
3. One could put the correct Ramsey Number, and a good set of coin flips, into an advice string. This would yield an algorithm in DTIME(n^{log n})/poly. A slighly weaker conjecture would suffice to prove this algorithm works.

FOCS Accepts

This list of FOCS accepts are out, with abstracts, with PDF links (via Kintali) and in Algorithmic Game Theory (Nisan) and Algorithms (Eppstein). The FOCS Conference will be held October 23-25 in Palm Springs.

Looks like a strong collection of papers. Lots of tight bounds. I'm a sucker for tight bounds because it means you have the right answer and less chance of follow-up papers.

Here are a few of the papers that caught my eye.

Randomness buys depth for approximate counting by Emanuele Viola. Buys you exactly two layers of AND-OR gates. Viola has another nice paper Extractors for circuit sources.

A Small PRG for Polynomial Threshold Functions of Gaussians by Daniel Kane. I like Gaussians because you can look at them at any angle and the distribution doesn't change.

Optimal bounds for quantum bit commitment by André Chailloux and Iordanis Kerenidis. Perfect quantum bit commitment is impossible but you can do better than classical. This paper shows exactly how well you can do.

Information Equals Amortized Communication by Mark Braverman and Anup Rao. A nice connection between information theory and communication complexity. I wonder if this can be tied into Kolmogorov complexity.