Skip to content

One Review, Three Storms

January 15, 2011


Can you work during a snow storm?

Bill Gasarch is famous for many things: basic research in computational complexity, reviews of countless books, and co-author of the original blog on computational complexity. The last was originated, of course, by Lance Fortnow.

Today I simply want to thank him for his recent review of my book (from p13 here).

Thanks Bill.

Bill is one of the founders of bounded-query complexity. Richard Beigel, who wrote his thesis on the subject, lists eight papers co-authored with Bill on this subject, some with other co-authors. See Bill’s survey here. Query complexity has come to our focus recently through its fundamental role in quantum computation.

Bill is also known for work in the nexus of additive combinatorics, Ramsey Theory, and recursion theory. He also organized a famous poll on the {\mathsf{P}} vs. {\mathsf{NP}} question. Some of the answers are serious, some funny, all are interesting—definitely check it out if you have not read it before.

Bill has been the long term reviewer of books for SIGACT News—the reviews are online here. This is a invaluable service to the theory community, and we owe him a great deal of thanks for this continuing stream of hard work.

Thanks again Bill.

Dick’s Storm—This Week

Bill’s review was one of the few bright spots for me this week; I have been snowed in, stuck at home, since a major storm hit Atlanta Sunday night. Supposedly we are “Hot’Lanta,” but we’ve been pretty cold and icy the last few days. In an unprecedented move Georgia Tech canceled classes for the first three days of the semester—even on the fourth day we were half closed. My class, on graduate theory for non-majors, was supposed to start Monday. Then it switched to Wednesday but got canceled again. My part of the city is still snowed-in and treacherous, so I decided to start the course next week.

The storm was not tiny—we got about 6 inches of snow. Then cool temperatures and lots of icing. The roads are a total mess. Of course the real problem is that we are not ready for this type of weather—unlike, say, Buffalo. Some local towns have no equipment. At least Atlanta has some, but clearly not even close to the amount of plows, sand trucks, and people needed to clear the streets. Our new governor announced that he thought the response to the storm was “adequate.” Oh well.

I raise this to ask the question: how does being “stormed-in” affect research? I have no definitive answer, but some partial thoughts that I would like to share.

Ken’s Storm—Years Ago

A storm negatively affected Ken’s activity during the 2006 world championship chess match, in which he answered an open request for help assessing statistical claims that one player was cheating with a computer between moves. Chess computers are so strong now that even world champions would like access to them during matches. I find this unsettling, but that is just how it is.

There has been almost no stormy weather in Buffalo all winter. Lake-effect bands south of the city account for most of Buffalo’s winter reputation. On Columbus Day, 2006, however, there was an incredible ice storm that killed or maimed a huge portion of of the area’s trees.

Ken had started his own blog during the world chess championship match in Sep.-Oct. 2006, in which he was involved in assessing computer-cheating claims made during the match. The storm came on the eve of the Friday tie-breaker, and knocked out power so Ken couldn’t join the live Internet commentary and talk about the negative conclusions he had just reached—no cheating. When his power was restored the following Monday he posted this about the storm, and this photo essay is now on his professional page too. It seemed an act that couldn’t be followed, so he stopped his blog.

That won’t happen here. Neither rain nor {\dots} will stop Ken and me from doing our thing.

Dick’s Storm—Decades Ago

You would think being snowed in would lend itself to lots of productivity. This week that was not my experience. I have been able to work on various things, but not as much as I would have liked. I think the forced isolation, where we could not even get out of our driveway, caused a cabin-fever effect.

Years ago, when I was faculty at Yale University in the late 1970’s, I got snowed in with Kelley Booth. Yale is in New Haven, which is in Connecticut which is well prepared for large snow storms. But this storm was huge and dropped two feet and closed the state. Cars were forbidden from the roads—it was one of the worst storms they had every had.

Kelly and I wound up spending two nights together in the downtown hotel near campus. Even though my house was only a few miles away, it was impossible to drive there from the hotel. I still recall eating dinner the first night at the hotel: we had steak and lobster, a wonderful meal. The second night the food was not so good. The hotel had a buffet of pretty meager pickings: we had some cold cuts and some stale bread.

Waiting out the storm Kelly and I had little to do, so we decided to try and prove some theorems. The result was a joint paper entitled: Computing Extremal and Approximate Distances in Graphs Having Unit Cost Edges. It was not the best result, but at least we had something to show for being snowed in together for 48 hours.

Open Problems

Do you know of other papers that have been written during a storm, or other state of emergency?

16 Comments leave one →
  1. January 15, 2011 11:23 am

    There’s also a list of book-review requests on Bill’s professional page.

  2. January 15, 2011 12:12 pm

    In his autobiography Random Curves: Journeys of a Mathematician , Neil Koblitz describes his productive use of enforced isolation in an Vietnam-era Army stockade:

    I asked my parents to bring me Serge Lang’s Algebra, which was one of the bst graduate-level textbooks. There is an old tradition in American prisons of allowing even prisoners in solitary to have one book—usually the Bible. For me, an atheist and aspiring mathematician, the “bible” was Lang’s textbook. I carefully read every page and solved every exercise problem.

    Our son has completed five combat tours in Iraq and Afghanistan as a US Marine, and it was quite instructive to compare his experience of the war with Koblitz’.

    Neil was imprisoned for distributing to his fellow soldiers a doctrinaire pamphlet from the (Maoist) Progressive Labor Party (PLP), titled Smash the Bosses’ Armed Forces. It is striking that at many of the social and political objectives that engaged Neil are echoed in today’s strategic doctrine for Marines, as summarized in Field Manual 3-24: Counterinsurgency:

    Cultural Forms

    A cultural narrative is a story recounted in the form of a causally linked set of events that explains an event in a group’s history and expresses the values, character, or self-identity of the group. Narratives are the means through which ideologies are expressed and absorbed by members of a society.

    For example, at the Boston Tea Party in 1773, Samuel Adams and the Sons of Liberty dumped five tons of tea into the Boston Harbor to protest what they considered unfair British taxation. This narrative explains in part why the Revolutionary War began. However, it also tells Americans something about themselves each time they hear the story: that fairness, independence, and justice are worth fighting for.

    As the Boston Tea Party example indicates, narratives may not conform to historical facts or they may drastically simplify facts to more clearly express basic cultural values. (For example, Americans in 1773 were taxed less than their British counterparts and most British attempts to raise revenues from the colonies were designed to help reduce the crushing national debt incurred in their defense.)

    By listening to narratives, counterinsurgents can identify a society’s core values.

    To my mind, this FM 3-24 passage expresses what weblogs like Gödel’s Lost Letter and P=NP are largely about: they are agoras that instantiate the STEM community’s present core values and narratives, at which we discuss what path(s) the future evolution of those core values and narratives *should* take.

    It is when we are “snowed in”—that is, relieved from mundane distractions—that these questions most easily surface in our minds.

  3. January 15, 2011 12:20 pm

    > Today I simply want to thank him for his recent review of my book (from p13 here).

    Very interesting review! The most interesting fragment I noted is “DOES HE REALLY THINK P = NP?”😉
    Thank you Prof Gasarch, thank you Prof Lipton.

  4. January 15, 2011 3:11 pm

    “Do you know of other papers that have been written during a storm, or other state of emergency?”

    What about this paper, by Leslie Lamport:

    http://research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html#trans

    “On the trip back home to California, I got on an airplane at Laguardia Airport in the morning with a snowstorm coming in. I got off the airplane about eight hours later, still at Laguardia Airport, having written this paper. “

  5. chazisop permalink
    January 15, 2011 4:33 pm

    There was also a positive thing about the snowstorm : More blogging!

    By the way, I think there is a small error in the post: “it was one of the worst storms they had every had” . I guess that is “they ever had”.

  6. January 15, 2011 4:56 pm

    A prominent example is Turán’s brick factory problem, an open problem in graph theory, which originated at the time when he was imprisoned in concentration camp during the Nazi regime.

  7. January 15, 2011 8:34 pm

    Thomas Jech’s “The Axiom of Choice” was written during “a long Buffalo winter”… that ought to mean a number of storms (with high probability).

    Reading it in sunny southern California I did experience a slight twinge of guilt.

  8. January 15, 2011 11:13 pm

    Three of my key results files still have their Oct 12, 2006 UNIX timestamps, including the separate runs of the pivotal Game 2 by me and my helper JB (Jason Buczyna):

    castor ls -lt KT*
    -rw-r–r– 1 regan 254204 Sep 2 2007 KT3log.txt
    -rw-r–r– 1 regan 4047 Sep 2 2007 KT1results.txt
    -rw-r–r– 1 regan 286154 Sep 2 2007 KT1log.txt
    -rw-r–r– 1 regan 220101 Oct 12 2006 KT4log.txt
    -rw-r–r– 1 regan 114038 Oct 12 2006 KT2logJB.txt
    -rw-r–r– 1 regan 4005 Oct 12 2006 KT2results.txt
    -rw-r–r– 1 regan 3611 Oct 12 2006 KT4results.txt
    -rw-r–r– 1 regan 5649 Oct 10 2006 KT3results.txt
    -rw-r–r– 1 regan 13318 Oct 5 2006 KTlog6.txt

    • January 16, 2011 8:14 am

      Ken, I am a big fan of of computer chess in general, and your writings in particular. Moreover, I am also a big fan of Robert Bixby’s article Solving Real-World Linear Programs: A Decade and More of Progress (2002).

      Bixby summarizes net improvements in the years 1988-2002 as follows:

         Algorithms: Algorithm * Machine ~ 2,360×

         Machines: Algorithm * Machine ~800×

         Net: Algorithm * Machine ~ 1,900,000×

      One wonders whether a Bixby-style analysis might be possible in computer chess?

      What would be your “Fermi Estimate” of the rate at which computer chess has improved?

      Are *most* forms of modeling and simulation witnessing a more-than-Moore speed-up?

      If so, why?

      And how long will more-than-Moore speed-ups continue?

      This last question is perhaps the most interesting of all …🙂

      • January 20, 2011 10:13 pm

        John, indeed I cover this in slide versions of my chess lecture. For me the operative concept is the “Depth” of a game. Define a “Class Unit” to be a difference in skill so that the stronger player expects to take 75% of the points from a weaker player. In chess Elo ratings this used to corresponding to a 200-point difference, though when the model switched from a bell-curve to a logistic-curve formulation that difference inched up to about a 76% expectation. Anyway, 200 rating points is called a “Class” in the US Chess Federation nomenclature, thus:

        2400+ Senior Master
        2200-2399 Master
        2000-2199 Expert
        1800-1999 Class A
        1600-1799 Class B
        1400-1599 Class C
        1200-1399 Class D
        etc.

        It used to be that 1200 was the default starting rating for an adult, and that regular players did not go much below 600, so with Fischer and Kasparov and a few more recently holding sway in the low 2800’s, I reckoned Chess as having a depth of 11 Class Units. (I forget the Hungarian person associated to this concept, another Laszlo Nagy?)

        I recall seeing estimates of Shogi at 12-14 class units, and Go way up at 25-40. Since each class unit is really a multiplication by 4, the depth of Go is incomparably higher,

        I used to think that progress of computers worked in class units over time in a consistent Moore’s Law-style fashion, but I’ve flipped around in the case of chess. Instead I feel the “draw graininess” of chess will retard progress around 3500 Elo. If a program rated 3100 can gain a draw against a hypothetical perfect player at least once every dozen games, then the “perfect” player will not get above 3500…

  9. Hajduk permalink
    January 16, 2011 2:46 pm

    I prefer writing papers during train rides😉

  10. William Gasarch permalink
    January 17, 2011 5:45 pm

    Being FORCED to NOT be at your computer (e.g., in a storm) can be very helpful.
    Note this Onion article

    • January 18, 2011 3:41 pm

      I think Bill is right—actually I wrote that to a friend recently. Nowadays smartphones and IPods can have you all-connected, all the time. We are not far from connectivity being symbiotic(?), to which I’ll add, alas.

  11. January 19, 2011 2:25 pm

    I got this today from my colleague Professor Stuart Shapiro, as part of general department chitchat not about this post, as an example of a paper written during a storm. (The chitchat was about humans evolving to be “wired”, and I’d contributed my son playing multiple simultaneous online games of Scrabble on his little IPod G4.)

    —————————————–
    Speaking of playing Scrabble on an iPod, you might be interested it the world’s first publication describing a program that plays Scrabble…[from] a 1977 Tech Report, later republished as S. C. Shapiro and H. R. Smith, A SCRABBLE crossword game-playing program. In D. N. L. Levy, Ed. Computer Games I. Springer-Verlag,
    New York, 1988, 403-419.
    Writing that Tech Report was how I spent the Blizzard of ’77. (plus a lot of shoveling)
    ————————————————-

Trackbacks

  1. Tweets that mention One Review, Three Storms « Gödel’s Lost Letter and P=NP -- Topsy.com

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s