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.