PCs, new folks, and new authors: some data

My post about SODA generated all kinds of comments: further discussion is in the comment threads. One point that merited another post:

A commenter complained:

I have noticed that most of the accepted papers in SODA/STOC/FOCS seem to be from one of the IVY league schools or from one of the established Labs...

Also, why in the world do we see the same set of names on program committees with little/no permutations.

I'll address both these points in some detail, accompanying my comments with statistics provided by Adam Buchsbaum (SODA 2005 PC Chair). First, let's look at the complaint about author diversity:

1. Diversity of authors:
What follows is a frequency chart of affiliations for a random sample of 27 (20%) of the accepted papers at SODA 2005:

6 max plank inst.
5 mit
4 u. illinois (u-c), tel aviv u.
3 u. bergen (norway), technion, hebrew u.
2 uc berkeley, u. waterloo, u. paris-sud, rutgers, ohio state u.
1 utrecht u., unsw (sydney), uc irvine, u. tokyo, u. leeds, u. glasgow, u. chicago, u. aarhus, stanford, simon fraser u., microsoft, kings college, it u. copenhagen, eth zurich, comenius u., cmu, christian-albrect u., charles u., acad. sci. czech republic

seems fairly diverse to me. It should not be hard to compile such stats for other years/conferences as well...

Next, let's look at the issue of recycling commitee members:

2. PC "freshness":

There is a perception that newer folks have a hard time getting onto S/S/F committees. To remedy this, David Johnson, at the SODA 2004 business meeting, introduced a list of 'neverbeens'. This list is defined somewhat roughly as

People who have never served on a S/S/F committee and plausibly could, where "plausibly could" includes things like

• out of school for at least some small amount of time
  
• some reasonable number (>= 1, more is better) of conference papers
• regular attendance at such conferences

He also requested that people who want to be on this list should email him. He then provides this list to commitee chairs to do with as they please.

But in reality, how skewed towards "frequent members" are program committees in reality ? Let's look at some numbers in detail.

Freshness of PCs:
For SODA 2005, roughly 1/2 (my earlier comment had said 1/3) of the PC members are new i.e have not served on a SODA/STOC/FOCS committee before (disclaimer: this set includes me). For SODA 2004, the corresponding number appears to be 1/3. Both numbers are reasonable, and might demarcate extreme ends of the "right" ratio.

Historical PC composition (all years):

1. SODA
Served exactly once: 130 people
Served exactly twice: 34
Served three times: 13
Served four times: 1

2. FOCS
1 time: 140
2: 52
3: 24
4: 14
5: 9
6: 4

3. STOC
1: 139
2: 49
3: 19
4: 8
5: 5
6: 2
8: 2

Overall: (SODA U FOCS U STOC)
1: 200
2: 84
3: 55
4: 34
5: 29
6: 5
7: 7
8: 9
9: 11
11: 1
12: 2
16: 1

(My take: SODA is better than STOC/FOCS at integrating new people, but not hugely so)

Adam further points out:

Translating these statistics to reflect recidivism in filling slots reveals that for each of the three conferences, a majority of the PC slots were filled by then-first timers. For all conferences as a group, the majority was filled by 1st- or 2nd-timers.

It thus seems to me that the perception of incestuousness among
FOCS, STOC, and SODA PCs is in fact a mis-perception. Still,
we have to address the mis-perception by ongoing action, not
simply historical statistics. David Johnson's maintenance of
a list of people who have never served on STOC, FOCS, and SODA
committees and a continuing effort to include new people are
positive forces.

Data is a good thing... If you don't like the stats here, do your own digging and I will post the results here.

The power of baseball...

So Tuesday I went to my first live baseball game, a Yankees game no less, courtesy of Adam. It was quite the cultural experience: I had 2 huge hot dogs, stood for the American National Anthem, stretched at the 7th inning stretch, even took cover from a whizzing fly ball screaming line drive (ed. baseball fans are picky...). Not to mention a full complement of home runs, double plays, intentional walks, grounds staff dancing to YMCA, and even a collision that left the catcher comatose for a few minutes.

The Yankees won 11-2 over Tampa, so there was good feeling all around. Clearly more good feeling than I expected....because....

Yesterday I got a letter from the Department of Homeland Security (nothing is guaranteed to strike more fear into a poor non-immigrant's heart) that said:

Your application for permanent resident status has been approved. Please take this notice, your Arrival/Departure rec....zzzzzz

As one might imagine, I tuned out at that point. I now have a green card !!! And I dare anyone to try and convince me that visiting a bonafide icon of the American cultural landscape had nothing to do with this: isn't this what the Patriot Act is for ?

Data collection...

Chandra asks:

It would be nice to know by some data analysis if we
have more people submitting papers or more papers
being submitted.

and says:

Good survey papers are really needed. CRC handbooks
also seem to do some of this indirectly although I wish the authors put up their articles on the web - who is going to pay hefty sums for these gargantuan sized books?

So I have two responses to this:

firstly, on the data collection issue, it is not as hard as one thinks. the data is available: all we need are PC chairs/members willing to extract and anonymize data appropriately, so no confidentiality is breached (do I really want people to know that I submitted 15 papers to SODA last year and they were all rejected?).

Secondly, although it is not really academically rigorous, I think that even blogs have a small role to play in helping spread the word about interesting developments in the field. Lance has been posting surveys about interesting papers/areas for a long time now, and my recent post on Arrow's theorem forced me to learn at least a bit more about social choice theory than I previously knew (and hopefully had something useful for readers).

I don't think blogs can replace rigorous reviewed surveys though, and somehow ACM Computing Surveys doesn't have the cachet of the various math review journals. There was some site (not arxiv.org) that allowed people to discuss the papers that were posted - that's an interesting idea as well.

What I feel (and people who've been around longer can correct me on this) is that we are at a volume level where we need to explore new strategies for disseminating (as opposed to publishing) research. Chandra makes a good point when he says that people are too busy publishing to write surveys (which are essentially useless from the point of view of tenure/grant commitees etc). Maybe all the tenured faculty out there need to step up :)

---

Update: Jeff Erickson deservedly swats me upside the head with a copy of Geometric Range Searching and its Relatives (incidentally one of the most useful surveys that I have ever read), and points me to (at least for geometry) a good collection of surveys maintained by Sariel Har-Peled. But of course we knew that geometry folks were ahead of the curve...

More SODA...

The review process was interesting for me: the discussions and reviews exposes one to a diversity of opinion and perspectives that one doesn't always get in one-on-one discussions, and there is a lot to learn.

Probably even more importantly, it gives me a better sense of what kinds of papers get into SODA. With the competition being what it is (this year I believe is a record low for acceptance), the goal changes from finding papers to accept to finding papers to reject, which means that papers have be a lot more polished, a lot more relevant, and a lot more interesting (at least to some subset of reviewers) than before. A paper that is overall decent has a tough battle, because of the sheer size of the submitted set.

The main problem of scale we face (and have been doing so for a few years now), is the reviewer load, (and at 65+ papers/person, we do have an issue). The question that really comes up is: is it that the (roughly) same set of people are writing more papers, or is it that there are just more people in the SODA community ? The answer is important, because it governs how we address the issue of reviewer load.

If there are overall more people entering the community, then it makes sense to continue to increase commitee sizes, expand conference durations and/or number of papers accepted (by shortening presentation times) and other such strategies. If it is that people are writing more papers, it is less clear what one can do about this, other than starting new conferences/journals...

Returning to the issue of reviewer load, I recently heard two different radical strategies that attempt to deal with different aspects of the problem.

* To handle the case of recycled papers that go from conference to conference in the hope of finding reviewers that haven't seen them:
- Create a repository where all submitted papers are registered. When a paper is submitted to a conference, a link is set up, and then when reviews return, they are filed with the paper. If the paper is submitted again, the reviews are there to see.

Main cons: public flagellation of papers is never a good idea, and authors could always create new entries to defeat this scheme

* To handle the issue of review quality and the perception of unfairness
- once papers have been accepted, make reviews for accepted papers public (anonymously).

The Rieman Hypothesis is the key to the Apocalypse

Via Not Even Wrong, an excellent synopsis of progress to date on the Poincare Conjecture.

Also, a link to a truly pointless article in the Guardian. I can sympathize with the plight of science writers; explaining some of the more abstract concepts in mathematics can be extremely difficult. But can you at least not be completely wrong ?

[If]... somebody really has cracked the so-called Riemann hypothesis, financial disaster might follow. Suddenly all cryptic codes could be breakable. No internet transaction would be safe.

Sigh.. later on comes this attempt to explain the first of the seven Millenium problems:

Birch and Swinnerton-Dyer conjecture: Euclid geometry for the 21st century, involving things called abelian points and zeta functions and both finite and infinite answers to algebraic equations

Why even bother...

As an aside, does anyone know why all of a sudden there is renewed interest in the Poincare conjecture ? There was a survey at least 3-4 months ago in the Scientific American about Perelman's work, and his first preprint was posted in 2002.

Voting and Geometry

It would be remiss of me (this is the Geomblog, after all) not to remark on the connection between voting and geometry pointed out by a commenter on my earlier post.

Donald Saari has developed an interesting theory of rankings based on mapping rankings to points in simplices. An immediate application of this formulation is the observation that the Kemeny rule determines a ranking minimizes the l₁ distance to the original ranking schemes.

Getting something named after you...

In an earlier post, I talked about the Condorcet criterion. As it turns out, this was discovered by Llull nearly 500 years before Condorcet formulated it.

Voronoi diagrams were first invented by Descartes, and then by Snow, and then by Dirichlet, before being invented by Voronoi.

The Koebe-Andreev-Thurston theorem relating circle packings to planar graphs was first proved by Koebe in 1936. Not knowing this result, Andreev re-proved it in 1970, and subsequently Thurston, who had proved it again, realized that his results followed from Andreev's work. All of this and more on circle packings is described here (PDF).

There are probably many other examples that establish the following meta-theorem.

To get a result named after you, be the last person to prove it.

A corollary might very well be:

To get a result named after you, publicize it everywhere.

SODA 2005...

results are out. The authors have been notified and a list should be available soon is here. A total of 135 accepted papers (the maximum possible given time constraints) out of roughly 490 submissions.

Arrow's Theorem, Voting, and Ranking Schemes.

In the light of Lance's post about voting schemes, it seems a good time to mention Arrow's theorem, the "impossibility theorem" for voting schemes. Arrow's theorem (and the related area of social choice theory) have become useful tools in computer science as well over the past few years.

The setting for Arrow's theorem is a set of rankings. Individuals (voters) order a set of options (candidates) via preferences, and the goal of a ranking scheme (voting system) is to come up with a preference list that respects certain properties:

• universality: the output should be a total order
• non-imposition: every possible order should be achievable
• non-dictatorship: the global preference should not merely follow one of the input rankings
• monotonicity: raising the ranking of a choice cannot hurt it in the overall rankings
• independence of irrelevant alternatives: the "spoiler" condition - rankings of options outside a given subset should not affect the ordering within the subset.

Arrow showed that all of these cannot be satisfied simultaneously (with at least two voters and three options). Incidentally, Arrow proved this in his Ph.D thesis, and it is one of the contributions mentioned in his Nobel Prize citation from 1972. His major work is most notably in the realm of pricing, and the Arrow-Debreu theorem on market pricing is a fundamental result that is familiar to people working in the area of mechanism design and auctions.

But social choice theory itself has been exploited in a CS context. To understand this, we need another notion, the Condorcet criterion.

One of the criticisms of Arrow's theorem is that the "spoiler" condition is too stringent, and other (weaker) conditions have been proposed that allow for a general voting procedure to exist. The most notable scheme is one that was developed nearly 800 years ago, and was rediscovered by Condorcet in the 18th century (which leads to a topic for another post). The idea is to create a ranking by looking at a series of face-offs. The relative ranking of options A and B is determined by seeing how many voters rank A above B, and taking the majority opinion. This is done for all pairs.

The Condorcet winner is then the option that in a head-to-head matchup beats all other options. Note that a Condorcet winner may not always exist, and this is the problem with using the Condorcet method in its basic form for elections.

The Condorcet criterion is a condition on a ranking scheme.

If any element beats all other elements in head-to-head matchups, it should be ranked first.

A generalization of this, the extended Condorcet criterion, states that:

If there is a partition (C, D) of the set S of options such that for each x in C and each y in D, x beats y head-to-head, then x should be ranked above y.

So what does all of this have to with computer science ? The application comes from the problem of merging ranked lists. The most common example of this arises when doing meta searches in a number of search engines. If Google ranks pages a certain way and Teoma does it a different way, how should the metasearch engine present results ?

The Condorcet criteria provide a condition that any reasonable ranking scheme must satisfy. The algorithms are generated by defining a metric on rankings, after which the consensus ranking is a good "center point" in the induced metric space. Specifically, if we define the "distance" between two rankings as the "bubble-sort" distance between them, or the number of pairs on which they disagree, then the Kemeny optimal ranking is the ranking that minimizes the average distance to all the input rankings. A nice property of the Kemeny optimal ranking is that it is the unique ranking satisfying the extended Condorcet criterion while having other desirable properties as well.

All of this is explained in some detail in the pioneering paper by Dwork, Kumar, Naor and Sivakumar. When I was at VLDB I saw more examples of these methods being used to merge the results of multiple rankings. I should add that the problem of merging different rankings comes up in many different settings, so it is worth knowing the background in social choice theory.

NIH Proposes Free Access For Public to Research Data

This opens up a new area in the evolving landscape of post-internet publishing:

The National Institutes of Health has proposed a major policy change that would require all scientists who receive funding from the agency to make the results of their research available to the public for free.

The proposal, posted on the agency's Web site late Friday and subject to a 60-day public comment period, would mark a significant departure from current practice, in which the scientific journals that publish those results retain control over that information. Subscriptions to those journals can run into the thousands of dollars. Nonsubscribers wishing to get individual articles must typically pay about $30 each -- fees that can quickly add up for someone trying to learn about a newly diagnosed disease in the family.

An interesting idea: Since most CS funding also comes from the NSF and the DoD (both tax-funded agencies), such an idea could easily float our way.

Sneakernet is validated !

A new article in the NYTimes confirms what we all learnt in networking 101:

...the problem will be familiar to anyone who ever spent time shrinking a digital photograph before trying to send it over the Internet through a dial-up connection. It would be much easier to drive a truck of photo albums across town or put them in an overnight-mail box than to go through the process of scanning and shrinking each photo.

The discussion came up in the discussion of interstellar communication. People at SETI were not amused:

The paper, Nature's cover article, is being received with bemusement by veterans of the Search for Extraterrestrial Intelligence, or SETI.

Dr. Paul Horowitz, a Harvard physicist and SETI expert, called it "a fun and an enjoyable read, but I wouldn't turn off my radio telescope and go out with my butterfly net."

Maybe it's just a train wreck.

Success catastrophe: a term I first heard in AT&T, used to describe a project that goes so well that higher ups keep demanding more and more (when you work at a company, being on the radar screen of the powers-that-be is a mixed blessing).

Catastrophe of success: Frank Capra's biography.

Catastrophic success: Apparently, the war on Iraq.

Any more suggestions ?

Talk styles

So I just finished my talk, and it appears to have been well received. Not being a DB regular, I took a somewhat more general tone with my slides, and listening to the other talks in my session, I realized that some notions I could have assumed audience knowledge for.

It brings up a duality in talk styles: does one:

* go into lots of details, explaining how specific things were done.
* present a general overview, glossing over details ?

As with all dualities, the answer is "it depends". On the one hand, if you give a talk where you say at some point, "And now we shall solve subproblem B with this trick that I won't get into in this paper", the people who came to your talk precisely because they had been banging their heads over subproblem B to no avail will be rather disappointed.

On the other hand, a lively and spirited discussion among 3 people about the solution to subproblem B might be lost on the 100 or so other people who have no clue as to why it was such a big deal.

My personal preference is what I'll call 'the big tent'. Keep things at a fairly high level, assuming that someone interested in the problem can read the paper with the roadmap one provides.

But (and here is where good judgement and the art of presentation comes in), make good choices about what details to present and what not to present. Some details are illuminating; some are not. Knowing which is which differentiates a good speaker from a not-so-good one.

What do DB people do ?

For people who know how I carp about databases in general, this will be deliciously ironic:

I was attempting to get my laptop to talk to the wireless system in the business center of the VLDB hotel, and the person managing the center comes up to chat. It turns out that he is taking computer classes in night school and asked me (of all people) what it is that database researchers do. It was interesting that his first thought was that they do something with Oracle. I think I successfully defended DB folk against this scurrilous baseless rumor...

As an aside, a friend of mine who used to teach databases to business school folks frequently complained that they all came into the class expecting to learn how to use Micro$oft Access.

Nosy gmail

Blogging will be light: am at VLDB in Toronto.

I was exchanging mail with a colleague about a problem in dynamic graph algos. I was doing this on my gmail acct for various reasons. I just noticed the ads that google placed next to the conversation:

1. Need an algorithm ?
2. Java graph layout library
3. Find shortest paths

Moreover, in the "related links" section, it pointed me to
(a) a paper on maintaining MSTs in graphs by Henzinger and King, and
(b) Information on Dijkstra's algorithm from NIST.

Spooky...

Graphics

In response to a previous post, Chandra asks:

Turing awards are typically given for work
that induce a paradigm shift. Not being very
knowledgeable about graphics, I would like to
know whether there have been any recent paradigm
shifts in graphics.

Hmm. I am not an expert, but here are some things:

• The switch from vector to raster graphics
• The use of specialized hardware (the graphics card) for rendering operations
• (and this is far too soon to tell) the advent of programmability in graphics cards.

all of these are fairly recent. It would be fair to say that much of the modern state of graphics reflects innovation that happened starting in the late 80s and going forward, and considering that the most recent Turing Award was given for something invented in the late 70s....

---

As an aside, wouldn't it be nice to have RSS feeds for comments ? I don't have any illusions that people are falling over themselves to hear what I have to say, but the only easy way for me to respond to comments in a way that they can find out is to reply directly (not always possible) or post a new entry.

Haloscan used to do this, but blogger doesn't... yet....

Referencing

I was chatting with people at SIGGRAPH and remarking on the fact that there is only one Turing Award winner for graphics (so far). The people there made the interesting argument that one of the reasons theoretical contributions appear to get Turing Awards more frequently (more on this below) is that theoretical papers tends to frame a problem in the context of related work far more meticulously.

Now this is something I have heard in other contexts as well (when seeing reviews of papers, reading papers etc). It is not too hard to see why this might be the case; theoretical problems are usually crisply defined, and it is almost always clear what results/techniques influence a given work (though not completely clear).

As an argument in favor of sound referencing, I like this one. We are taught (implicitly or explicitly) that referencing is important to place work in context, to acknowledge other's work in the "society of research", and ultimately to recognize that one's one work is never done in isolation but builds upon that of others. The argument that proper referencing creates a trail back to a source of inspiration is more than 'citation counts count !': it emphasizes what's important about careful referencing: that it builds a structured edifice of knowledge whose value can be perceived objectively.

Back to Turing Awards:

According to my highly unscientific classification method, theory-like disciplines (Algorithms/Complexity/Logic/Programming Languages) took a large, but not overwhelmingly large share of Turing Awards:

(Contains theory-like substance): 18 (11 Alg/Complexity + 6 PL + 1 Logic)
(We build stuff): 10 (3 DB + 7 Compilers/Arch/OS/)
(We are stuff): 5 (4 AI/1 Robotics)
(We count stuff): 2 Numerical Analysis

What category does Dijkstra fall into ? I left him out of this...

War and Graphics

A few days ago, on the SIGGRAPH blog, I remarked on the number of simulations directed towards military applications. Now this kind of thing has been going on for a while within the graphics community, and I am sure none of them are surprised by this.

However, in what can only be viewed as a sign of the times (no pun intended), both the New York Times Magazine and the September issue of Wired carry articles describing the level of sophistication military simulations have reached in training soldiers for combat situations. Both articles focus on a particular software package called Full Spectrum Warrior as one of the primary candidate tools for training soldiers (FSW is available as a commercial tool; the military version has more features and more accurate military plans than the commercial version).

The focus (contrary to the popular impression conveyed by games like Doom and Quake) is not on first-person orgies of murder and mayhem; many of these simulations, and indeed many games nowadays, focus more on story telling and scenarios/strategies. Some military training game don't even allow the player to fire a weapon, requiring that they handle situations without the use of force.

The NYT article gets bonus points for managing not to mention Ender's Game. The Wired article stays strong for a while, and then flubs the ending, not only mentioning the book, but mangling the title.

---

p.s The game industry is paying their PR staff well...here's how games are taking over Hollywood

p.p.s More coverage of this on /. (follow the links in the blurb)

Open Problems (redux)

One of my first posts was about finding interesting problems to work on. Adam Klivans, guest-posting over at the complexity blog, mentions that COLT has an extremely civilized approach for dealing with this:

For the last few years, COLT has glorified the open problems section and allocates about an hour of time for a presentation of open problems. The open problems themselves must be submitted months beforehand and are refereed (how rigorously is anyone's guess); accepted problems appear in the proceedings. A list of this year's open problems can be found on the COLT 2004 program schedule -- the session was held on Friday evening.

Thus I am happy to note that this year's fall workshop on computational geometry will have a similar focus on open problems. From the call for abstracts:

To promote a free exchange of questions and research challenges, there will be a special focus on Open Problems, with a presentation on The Open Problems Project, as well as an Open Problem Session to present new open problems. Submissions are strongly encouraged to include stand-alone open problems, which will be collected into a separate webpage and considered for inclusion in The Open Problems Project.

This workshop is the 14th in a series of CG workshops that are always a pleasure to attend: the focus is on interactions and discussions, rather than presentations, and the atmosphere is always very relaxed. So mark your calendars for Nov 19-20 in Boston.

Timing a talk

A nifty link I found via the Dynamist Blog:

It's an online stopwatch to time yourself. Handy if you're like me and never carry a watch, and need to time yourself when preparing a talk.

A survey on inapproximability

Not to infringe on the Complexity blog :), but I found this survey by Luca Trevisan at the ECCC to be a very well written birds-eye view of the developments in inapproximability from slightly before the main PCP results till now (in fact some of the results mentioned are to appear at FOCS 2004).

It covers the early attempts at showing approximability by gap-introducing reductions, spends a little time (although not a lot) on the growing body of work relating proof systems to inapproximability, and then spends a lot of time on developments post PCP.

What I like about it, as a non-expert in complexity, is that it explains some of the basic PCP-based methods for proving hardness very lucidly, using examples like clique and set cover. It also helps one understand the feverish developments in the field leading to the slew of optimal inapproximability results in the late 90s.

There has been a recent flurry of breakthrough complexity results, some of which are to appear at FOCS. The survey addresses some of these new results as well, and what they could imply for the knottier problems like vertex cover etc.

Probably one of the most interesting developments over the past few years is a set of hardness results that destroy the 5-class inapproximability hierarchy that people had thought to map out the space of approximations. New results showing tight log^* n hardness, log log n hardness, and even log² n hardness results indicate that approximation classes might be a lot finer than people had imagined.

What is it ?

I was wandering the corridors of AT&T one day and picked up a gizmo that looked like this:

Rather puzzled by it, I took it to lunch, where I was peremptorily ridiculed for basically being too young to know what it was. As it turns out, this is the "type ball" of the IBM Selectric, an ingenious gadget that allowed one to change types on the fly (the ball had all the characters of a particular type on it, and would rotate as keys were pressed on the typewriter.

This story would be highly unremarkable if not for the fact that William Gibson, author of Neuromancer and cyberpunk pioneer, wrote a little rhapsody to the Selectric type ball.

[Dead Tech backgrounder, for extra points: In the decade or so prior to the advent of personal computers, IBM produced an electric typewriter called the Selectric; this had a “type-ball”, a metal sphere about the size of a golf ball, which held an entire font; you could switch fonts, which at the time was little short of miraculous; you could also, even more amazingly, power-correct mistakes with a built-in paper-colored ribbon. The IBM Selectric, when I started writing for publication, was the most shit-hot professional writing machine on the planet; by the time I could have afforded one, they were propping up broken barbecue grills in Value Village. The Finn’s shop probably has at least one box of Selectric type-balls, somewhere; they are beautiful sculptural objects, these balls, and won’t be easily thrown away.]

PCPs for geometric problems

Many geometric problems (especially those involving rectangles in the plane) are MAX SNP-hard; some are even log n hard via set cover reductions, and there is at least one problem (matching of point sets) that is polynomially hard.

However, as far as I am aware of, most of the reductions are via L-reductions from other hard-to-approximate problems. In fact the only "from first-principles" hardness results for geometric problems (i.e directly from a PCP) that I am aware of are

1. The result by Brieden showing that width is hard to approximate to any constant
2. The extension by Varadarajan, Venkatesh and Zhang that shows it is hard to approximate to within log^d n, for some d > 0.

In both cases, the "source" problem is Quadratic Programming. One might quibble that even in this case, the reduction is really an L-reduction from QP, but in both results some tinkering with the PCP is necessary to get the desired bound.

Are there other problems that have "from first principles" hardness results ?

A trail of thought...

The knowledge contained in a research paper represents only a small fraction of the trips the author(s) took through the landscape of the subject. There are countless counterexamples, lemmas that didn't work, statements that were trivial, and ideas that fell by the wayside, none of which make it into a written document, and only occasionally see the light of day (in a casual talk, or a one-on-one conversation).

But these lost trails are useful as well. they are landmarks of places not to go, of things unexplored, of directions taken and backed away from. It is a pity that one cannot record these as part of the research log, in some form.

Vannevar Bush talked about these things nearly 60 years ago, in a prescient essay titled 'As We May Think'.

This is the essential feature of the memex. The process of tying two items together is the important thing.

When the user is building a trail, he names it, inserts the name in his code book, and taps it out on his keyboard. Before him are the two items to be joined, projected onto adjacent viewing positions. At the bottom of each there are a number of blank code spaces, and a pointer is set to indicate one of these on each item. The user taps a single key, and the items are permanently joined. In each code space appears the code word. Out of view, but also in the code space, is inserted a set of dots for photocell viewing; and on each item these dots by their positions designate the index number of the other item.

Thereafter, at any time, when one of these items is in view, the other can be instantly recalled merely by tapping a button below the corresponding code space. Moreover, when numerous items have been thus joined together to form a trail, they can be reviewed in turn, rapidly or slowly, by deflecting a lever like that used for turning the pages of a book. It is exactly as though the physical items had been gathered together to form a new book. It is more than this, for any item can be joined into numerous trails.

The owner of the memex, let us say, is interested in the origin and properties of the bow and arrow. Specifically he is studying why the short Turkish bow was apparently superior to the English long bow in the skirmishes of the Crusades. He has dozens of possibly pertinent books and articles in his memex. First he runs through an encyclopedia, finds an interesting but sketchy article, leaves it projected. Next, in a history, he finds another pertinent item, and ties the two together. Thus he goes, building a trail of many items. Occasionally he inserts a comment of his own, either linking it into the main trail or joining it by a side trail to a particular item. When it becomes evident that the elastic properties of available materials had a great deal to do with the bow, he branches off on a side trail which takes him through textbooks on elasticity and tables of physical constants. He inserts a page of longhand analysis of his own. Thus he builds a trail of his interest through the maze of materials available to him.

And his trails do not fade. Several years later, his talk with a friend turns to the queer ways in which a people resist innovations, even of vital interest. He has an example, in the fact that the outranged Europeans still failed to adopt the Turkish bow. In fact he has a trail on it. A touch brings up the code book. Tapping a few keys projects the head of the trail. A lever runs through it at will, stopping at interesting items, going off on side excursions. It is an interesting trail, pertinent to the discussion. So he sets a reproducer in action, photographs the whole trail out, and passes it to his friend for insertion in his own memex, there to be linked into the more general trail.

There are many more gems in the essay: worth a read.

---

My link trail: Boing Boing -> Battelle On Search.

Perl Swearing

In this article, Paul Graham comes up with a really funny description of Perl:

"When I talk about ugly source code, people will of course think of Perl. But the superficial ugliness of Perl is not the sort I mean. Real ugliness is not harsh-looking syntax, but having to build programs out of the wrong concepts. Perl may look like a cartoon character swearing..."


The article is about Python programmers: makes for interesting reading.

---

p.s SIGGRAPH is finally over. It was overwhelming, fascinating, boring, and LONG; all at the same time. My conference-ending-timer kicked in around Monday, and it has been a long haul since.

Real vs "Real"

From the SIGGRAPH blog:

An undercurrent that occasionally bubbles up in talks/comments is the feeling that graphics is "not real", that it is only "smoke and mirrors". Bruce Sterling (when he wasn't busy being pleased with himself) hammered this point home as well during the beginning of his keynote address. Given that from where I stand in theory-land, graphics is about as "real" as it gets, this was interesting and not a little surprising.

Read more...

I've been spotted !

It appears that my SIGGRAPH entries over the past few days have not gone unnoticed. I was invited to post entries to the official SIGGRAPH blog. I will be crossposting my most recent entries there, and will be posting new notes there.

I'll also provide a brief summary (and links) here in case people don't want to switch over.

Demo or Die...

Another interesting concept at SIGGRAPH is called 'Demo or Die'. The premise is as follows:

* you have to conduct a live demo of whatever gizmo you've cooked up.
* you get three minutes to present it
* After your demo, the audience gets to vote.

Now the voting itself is a neat idea. The organizers distributed laser pointers (yes, over a 1000 of them) to everyone in the audience. There was a large screen up near the speaker podium, and after each demo, two large boxes saying Demo and Die were broadcast on the screen. You pointed your laser pointer at the screen (these are very powerful pointers) and with some nifty software/hardware, the number of dots on each side were tallied to decide whether the presentation survived or not.

Surprisingly enough, the Law of Demos only kicked in once; most demos ran seamlessly. Which is not to say that they were all good. Some were quite nifty, involving haptic devices.

An amusing moment: A demo participant from Microsoft showed a haptic device for playing Jenga online. I had dinner with him the night before, and he was describing the demo to me. I couldn't help but remember Uri Zwick's talk on Jenga from SODA 2002. It seemed fitting that we prove theorems about Jenga, while graphics people build demos about Jenga.

Stranger in a strange land...

So after the somewhat more civilized GP2 workshop, I am now at SIGGRAPH itself. It's being held in the LA convention center, and if any of you have ever been to a home improvement or other such convention, you will get an idea of the scale of this beast.

The main order of business is the Fast Forward Paper Review: the idea is that all authors of the 83 accepted SIGGRAPH papers get 50 seconds to present a capsule preview of their work. It's an interesting concept, and with over 2,000 people (out of 20,000) attending the conference itself, it is probably essential.

The review itself is held in a dark and cavernous curtained-off section of the convention center. Joe Marks, the PC chair, just announced the start of the review, and from the sound of the applause, you'd think you were at a rock concert.

It's quite the setting: there are three huge screens for the presentation and another huge screen displaying the presenter. Not all the presenters are good at this format though: some people run through reduced versions of their actual presentations. Powerpoint never looked so out of place...

Some highlights:
1. Rendered gems that look like real !!
2. Graphical origami: how to make a paper model from a mesh. You CAN Touch this !
3. Triangles are toast; Our very own Nina Amenta renders with point clouds.
4. A Mission-Impossible-themed movie....on tensors.


Random thoughts:
* You can tell that this is Hollywood-driven: many presentations go "suppose you have this picture, and your director wants it modified to that picture"
* It does put paper-writing in perspective: how many paper ideas would survive if you knew you also needed a funky 50 second advertisement for them ? Reminds of the maxim (by Feynman?): if you can't explain what you are doing in one sentence to a child, you are probably not doing anything interesting.

Heard in passing...

Things heard at the GP2 Workshop:

Fred Brooks:
In the days of IBM 7950 (1961), you would program one 250 byte instruction, go for lunch, program one more, and then leave for the day.

Keith Cooper:
In 1980, a compiler could generate code that ran at 85% of peak CPU power (on a VAX). The figure now is 5-15%.

Hi ho, hi ho,...

it's off to SIGGRAPH I go...

A rite of passage that many fellow geometers have gone through: I will be hanging out with the only group of people who can hope to get both Turing awards and Academy awards (take that, C. P. Snow).

<shameless-shill-for-my-research>
I go to do God'sTuring's work: presenting some results on theoretical analyses of GPU algorithms at the GP2 workshop. If I can make it through the workshop without getting into any arguments about the value of theory, I will consider it a success.
</shameless-shill-for-my-research>

SIGGRAPH gets over 2,000 attendees; considering how we do cartwheels at SODA when we get 300 folks, I expect significant culture shock.

Update: Did I say 2,000 ? I mean 20,000. Sigh....

Scott Aaronson is a very patient man...

The latest P=NP saga on comp.theory involved soap bubbles: the first post in the thread:

The paper is the best argument I have heard for P=NP, even though I believe the opposite. It can be found here: http://arxiv.org/abs/cs.CC/0406056. It brings out a great question.

Basically, the argument is that since soap bubbles can be made to solve NP-complete problems, particularly the Steiner tree graph problem, in what appears to be polynomial time and physics on a macroscopic level can be modeled as a Turing machine, it must be true that P=NP.

What I would like to know from any physicists out there is why do soap bubbles work in such a way that they are able to solve the Steiner tree graph problem?How is nature able to quickly solve problems that we cannot solve quickly?

Scott Aaronson, in a post downstream:

Motivated by this newsgroup discussion, this week I did the experiment. At a hardware store I bought two 8"x9" glass plates; paint to mark grid points on the plates; thin copper rods which I cut into 1" pieces; suction cups to attach the rods to the plates; Murphy liquid oil soap; and a plastic tub to hold the soapy water. I also bought work gloves, since at one point I cut my hand handling the glass.

The post continues: read it all. He even has a picture.

Proofs and Reputations

Karl Sabbagh, the author of a recent book on the Riemann Hypothesis, recently wrote an article in the London Review of Books about Louis de Branges and his recent announcement of a proof for the RH.

There is no evidence that, so far, any mathematician has read [de Branges' proof ]: de Branges and his proof appear to have been ostracised by the profession. I have talked to a number of mathematicians about him and his work over the last few years and it seems that the profession has come to the view that nothing he does in this area will ever bear fruit and therefore his work can be safely ignored. It may be that a possible solution of one of the most important problems in mathematics is never investigated because no one likes the solution's author.

My post has nothing to say about the proof itself; I would not dare to presume even a passing familiarity with it. What caught my attention was the sense of surprise in Sabbagh's article; the unstated 'what on earth does a man's reputation have to do with his proof' ?

What indeed ?

Mathematics (and by extension theoretical CS) inhabits a Platonic world of truths and false statements (with a dark brooding Gödel lurking in the background, but that's a different story). As such, either statements are true, and become theorems/lemma/what-have-you, or they are not and fall by the wayside. The pursuit of (mathematical) truth is thus the search for these true statements. The identity (or very existence) of the searcher has no effect on the truth of the statements; there is no observational uncertainty principle.

However, mathematicians live in the real world. In this world, true and false gets a bit murkier. A theorem is no longer true or false, but almost certainly true, or definitely false. They are far closer to the falsifiable theories of natural science, although there is at least a "there" there; a scientific theory can only have overwhelming evidence in support of it, but a mathematical statement (if not too complex) can be categorically true.

The natural sciences have reproducible experiments; if I cannot reproduce the results you claim, all else being equal, the burden of proof is on you to demonstrate that your results are indeed correct. Similarly in mathematics, if a claimed theorem has a complex proof, the burden of proof does reside on the author to demonstrate that it is indeed correct. They can do this by simplifying steps, supplementing with more intuition, or whatever...

In this respect, theorem proving in the real world has a somewhat social flavor to it. And thus, there is also (it seems to me) a social compact: You demonstrate competence and capability above a certain basic threshold, and I deem your proofs worthy of study. The threshold has to be low, to prevent arbitrary exclusion of reasonable provers, but it cannot be nonzero zero, because in the real world it is hard to check a proof with absolute certainty.

This is why the many proofs that P=NP (or P != NP) that float on comp.theory don't get a fair shake: it is not because the "experts" are "elitists" who don't appreciate "intruders" poaching their beloved problems; it is because the social compact has not been met; the writers don't cross the threshold for basic reasonableness, either by choosing to disregard the many approaches to P vs NP that have been ruled out, or by refusing to accept comments from peer review as plausible criticism, and demanding that the burden of proof be shifted from them to the critical reviewer.

Such a compact could be abused mightily to create a clique; this is why the threshold must be set low and is low in mathematics. The notorious cliche that a mathematician's best work is done when young at least reinforces the idea that this club can be entered by anyone. More mundanely, there are awards for best student papers at STOC/FOCS that often go to first-year grad students (like this year's award).

Going back to de Branges' proof, I have no idea what the technical issues are with his proof, and if there are known reasons why they don't work, but going solely on the basis of Karl Sabbagh's article (and I acknowledge that he could be biased) it seems wrong to ignore his manuscripts. He for one has clearly crossed the threshold of the social compact. Reminds me of an attempt I made to read a popular exposition of Mulmuley and Sohoni's recent work on P vs NP; if this work does lead to a claimed proof, I imagine that there would be few people who could comprehend the proof, but it would deserve to be read.

On empirical research and the Energizer Bunny

From Lee Smolin's article on the anthropic principle:

...to be part of science, X-theorists have to do more than convince other X-theorists that X-theory is true. They have to convince all the other well trained scientists who up till now have been skeptical. If they don’t aspire to do this, by rational arguments from the evidence, then by Popper’s definition, they are not doing science.

From Numerical Recipes in C (Ch. 14, pg 609):

At best, you can substantiate a hypothesis by ruling out, statistically, a whole long list of competing hypotheses, every one that has ever been proposed. After a while your adversaries and competitors will give up trying to think of alternative hypotheses, ro else they will grow old and die, and then your hypothesis will become accepted. Sounds crazy, we know, but that's how science works.

So that's where the creationists get their methods from !

From an interview with Lawrence Kraus in Scientific American:

But then you realize that this is exactly what Phillip Johnson, this lawyer who first proposed the intelligent-design strategy, proposed when he said something like, "We'll just keep going and going and going till we outlast the evolutionists."

Sorting vs Searching:

In a previous post, I had mentioned an upcoming paper in FOCS 2004 by Franceschini and Grossi titled 'No Sorting? Better Searching!'.

The paper is not yet online, but Roberto Grossi posted a long comment in that post detailing the results in the paper. I reproduce the comment below in full; a short summary is:

They show that the natural way to do searching in a set of ordered elements (i.e via sorting and then doing binary search), makes sense when the cost of comparisons is O(1), but does not make sense when elements are larger (formally, when each element of the list actually consists of k characters, where k is super-constant). They do this by demonstrating a new ordering technique that beats known lower bounds on searching a sorted list; what's nice is that their result is tight as well.

His abstract follows (bold-face is mine):

Sorting is commonly meant as the task of arranging keys in increasing or decreasing order (or small variations of this order). Given n keys underlying a total order, the best organization in an array is maintaining them in sorted order. Searching requires Θ(log n) comparisons in the worst case, which is optimal. We demonstrate that this basic fact in data structures does not hold for the general case of multi-dimensional keys, whose comparison cost is proportional to their length. In previous work [STOC94, STOC95, SICOMP00], Andersson, Hagerup, Håstad and Petersson study the complexity of searching a sorted array of n keys, each of length k, arranged in lexicographic (or alphabetic) order for an arbitrary, possibly unbounded, ordered alphabet. They give sophisticated arguments for proving a tight bound in the worst case for this basic data organization, up to a constant factor, obtaining

Θ[ (k log log n)/(log log (4 + (k log log n)/(log n)) + k + log n ]

character comparisons (or probes). Note that the bound is Θ(log n) when k=1, which is the case that is well known in algorithmics.

We describe a novel permutation of the n keys that is different from the sorted order, and sorting is just the starting point for describing our preprocessing. When keys are stored according to this ``unsorted'' order in the array, the complexity of searching drops to Θ( k + log n) character comparisons (or probes) in the worst case, which is optimal among all possible permutations of the n keys in the array, up to a constant factor. Again, the bound is Θ(log n) when k=1. Jointly with the aforementioned result of Andersson et al., our finding provably shows that keeping k-dimensional keys sorted in an array is not the best data organization for searching. This fact was not observable before by just considering k=O(1) as sorting is an optimal organization in this case.

When the paper is available I will link to it here; one interesting question is: how hard is this "other" order to compute ?

That wonderful feeling of nothing...

A friend of mine just defended his Ph.D successfully (congratulations, Nabil !), and sent me this excerpt (extracted from here) in response to my email congratulating him:

In February 1995, on a beautiful sunny day with clear Carolina blue skies, I turned in the final,signed copy of my dissertation. The graduate school staff member did some last-minute checks on the document and pronounced it acceptable. After six and a half years of toil and sweat, I was finally done! While walking back to the C.S. department building, I was sorely disappointed that the heavens didn't part, with trumpet-playing angels descending to announce this monumental occasion. Upon hearing this observation, Dr. Fred Brooks (one of my committee members) commented, 'And the sad fact is, you're no smarter today than you were yesterday.'"


Another amusing take on graduate student life, from the same article:

Being a graduate student is like becoming all of the Seven Dwarves. In the beginning you're Dopey and Bashful. In the middle, you are usually sick (Sneezy), tired (Sleepy), and irritable (Grumpy). But at the end, they call you Doc, and then you're Happy.

Path compression...

The main takeaway from the Seidel-Sharir paper refining the analysis for union-find, as explained to me by Adam Buchsbaum (who is still walking the corridors in amazement):

If path compression takes linear time, then it takes α(n) (amortized) time.

Truly amazing. Worth reading just for that...

Topology rules the playground !

This is the last place you'd expect to see a lucid discussion of topological concepts:

Boing Boing: Double twist strip playground equipment

Why do algorithm engineering ?

I was listening to a talk today where the speaker made the following statement: 'We know that this works well in theory, and now we'd like to see if it works well in practice'. Now this is a statement I have probably heard hundreds of times over the past many years, and it is in no way noteworthy or unusual.

However, it did get me thinking. It is by now a truism that no one will seriously dispute that there is often a gap between the theoretical predictions offered by an algorithm analysis and the behaviour of this algorithm in practice. Contrary to what many people would conclude, this is of course not a black mark on the value of theoretical work. The power of algorithm analysis, poly-time, and even the much maligned O() notation, lies in the invariance of (classical) machine definitions under poly-time transformations, and the powerful mathematical structure that complexity theory acquires as a result.

This structure does have a tradeoff; we get mathematical elegance, but lose a certain modicum of "predictiveness" when it comes to analysing the behaviour of an algorithm "in practice". And I think herein lies the true value of algorithm engineering. If the algorithm that has better theoretical guarantees does better in practice (and this happens more often than one thinks), one's task is complete; if not though, all is not lost. Often, peculiarities in the data cause certain algorithms to behave better than others, even though from an asymptotic perspective a different outcome would be expected. Sometimes, analysing the running time is not the right measure: output-sensitivity in geometric algorithms is an example of a measure that captures certain desirable properties that can be missed with a blunt-edge worst-case running time.

But ultimately, the goal of algorithm engineering, or of good experimental algorithmic work, is to tease out the tradeoffs, parameters and special cases that govern which algorithm is the right one for a specific setting. If I am a practitioner, I am less interested in knowing the algorithm with the best asymptotic efficiency than I am in knowing which algorithm can provide the best performance for my situation. This does not mean that we should throw proofs out of the window: it means that often a much more delicate analysis of the behaviour of an algorithm is required in order to determine what works better.

---

I think I just wrote an ALENEX manifesto. Oh well :)

A Pentium III ?

From Forbes, via the Computing Research Policy blog (emphasis added):
Meanwhile, another even more serious threat to the U.S.' competitive position in supercomputing is lurking in the shadows. Tucked away into the House version of the National Defense Authorization Act, which passed in May, is Section 1404, which would classify any computer using a Pentium 3 processor or stronger as a 'militarily critical' machine to the Department of Defense--or, a weapon--and make it subject to tightened export regulations. While high-performance computers are already regulated separately as part of a 1991 agreement with Japan, called the Supercomputer Control Regime, the new restrictions would arguably affect certain systems components developers need for supercomputers.

If a Pentium III can be classified as military weaponry, suddenly I don't feel so safe anymore.

GR conferences are more interesting than one might imagine

This is from John Baez's latest column describing the frenzy at a general relativity conference in England where Stephen Hawking conceded the bet he and Kip Thorne made with John Preskill:

A fellow with long curly grey locks and round horn-rimmed glasses sat down beside me. I'd seen him around the conference, so I said hello. He asked me if I'd like to hear about his theory; at this point my internal alarm bells started ringing. I told him I was busy, but said I'd take a look at his manuscript later.

It turned out to describe an idea I'd never even dreamt of before: a heliocentric cosmology in which the planets move along circular orbits with epicycles a la Ptolemy! And his evidence comes from a neolithic British tomb called Newgrange. This tomb may have been aligned to let in the sun on the winter solstice, but some people doubt this, because it seems the alignment would have been slightly off back in 3200 BC when Newgrange was built. However, it's slightly off only if you work out the precession of the equinox using standard astronomy. If you use his theory, it lines up perfectly! Pretty cute. The only problem is that his paper contains no evidence for this claim. Instead, it's only a short note sketching the idea, followed by lengthy attachments containing his correspondence with the Dublin police. In these, he complained that people were trying to block his patent on a refrigerator that produces no waste heat. They were constantly flying airplanes over his house, and playing pranks like boiling water in his teakettle when he was away, trying to drive him insane.

Things to do with an iPod...

courtesy BoingBoing:

1. Have drink
2. Eat pizza
3. Find loo...

Entertaining audio reviews and even accompanying sound tracks such as Handel’s ‘Water Music’ and ‘Cosmic Winds’ will help users to locate their nearest (and loveliest!) loos.

---

For people challenged in the Queen's English, loo = restroom.

Black holes mangle matter and energy, but cricket IS better !

I had recently mentioned Hawking's retraction of his claim that a black hole destroys everything that enters it. He has now presented his work at a conference on GTR.

A footnote to this story is the famous bet that Hawking and Kip Thorne (of CalTech) had with John Preskill (also at CalTech). The terms of the bet were:

"information swallowed by a black hole is forever hidden and can never be revealed."
Preskill bet against that theory.

The forfeit is an encyclopedia, from which Preskill can recover information at will.


Since Hawking lost the bet, he owed Preskill an encyclopedia:

He presented Preskill a favored reference work "Total Baseball, The Ultimate Baseball Encyclopedia" after having it specially flown over from the United States.

"I had great difficulty in finding one over here, so I offered him an encyclopedia of cricket as an alternative," Hawking said, "but John wouldn't be persuaded of the superiority of cricket."


However, the matter does not appear to be resolved:

But Preskill says that Hawking's new take on quantum gravity rests on shaky mathematical foundations, and is unlikely to be embraced by the physics community. "I am sceptical about whether he has found a fully satisfactory resolution to the problem," he says.

What's eccentric about that ?

From the Fields Medal citation for Tim Gowers:

Banach was an eccentric, preferring to spend his time in the café rather than in his office in the University of Lvov

sounds reasonable to me...

The Two Cultures...

Michael Nielsen, in his ongoing series on the principles of effective research, talks about problem solvers and problem-creators as two models of research:

The problem-solver: This is the person who works intensively on well-posed technical problems, often problems known (and sometimes well-known) to the entire research community in which they work. The best problem-solvers are often extremely technically proficient and hard-working. Problem-solvers often attach great social cache to the level of difficulty of the problem they solve, without necessarily worrying so much about other indicators of the importance of the problem.

The problem-creator: This is a rarer working style. Problem-creators may often write papers that are technically rather simple, but ask an interesting new question, or pose an old problem in a new way, or demonstrate a simple but fruitful connection that no-one previously realized existed.

In an interesting coincidence, Chandra Chekuri just pointed me to Tim Gowers' (the 1998 Fields Medallist) website. There, Prof. Gowers has an article titled 'The Two Cultures', where he talks essentially about the same schism in mathematics, between problem solvers, and theory builders.

It is interesting to compare the two reflections. Nielsen feels that the 'problem-creator' style is rarer, and "less popular" than the problem-solver mode. In Gowers' view, theory builders look down on problem solvers (for example, people who do combinatorics) because of a perceived "lack of depth" and other such reasons.

The two polarities are not quite the same; but read together they provide a thoughtful perspective on the kind of schisms that we all face in our research work. I can definitely attest to feeling the kinds of conflicts they talk about, between 'solving problems' and 'building theories'.

Somehow writing a blog itself seems to fly in the face of Hardy's dictum:

There is no scorn more profound, or on the whole more justifiable, than that of the men who make for the men who explain. Exposition, criticism, appreciation, is work for second-rate minds..

Browsing the amazing list of expository articles at Gowers' website, it is comforting to see this shibboleth too go by the wayside.

Reading Harry Potter makes you very smart...

Today I got an email from Amazon.com (emphasis added)

Dear Amazon.com Customer,

As someone who has purchased books by J. K. Rowling, you might like to know that "Harry Potter and the Philosopher's Stone (Ancient Greek Edition)" will be released soon. You can pre-order your copy at a savings of 30% by following the link below


I knew that reading is good for you, but I didn't know that reading Harry Potter was that good for me...

Pacing...

The virtues of pacing are highly underrated. When you have over 60 submissions to review, the immenseness of the task can completely drown out all rational thought. The number of papers to be reviewed on a per-day basis is not that bad, but you have to stick to a routine !

Taking breaks is also a good thing: I finished my quota today, and I shall now soothe my fevered brow with a good helping of topological spaces via Claude Chevalley. Aaaahh.....

Useful trivial answer

Probably my first exposure to science fiction was via Isaac Asimov, and his robot books. I am shuddering at the thought of what the movie version of I, Robot did to his vision, and the review in Slate is not encouraging.

This little nugget of information is fascinating, and should be a Jeopardy question:

"By the end, Asimov achieved the Grand Slam of book writing, turning out at least one volume for each of the 10 classifications in the Dewey Decimal System."

Conferences and the e-print server at LANL

Lance has a nice post on the reason why conferences are so much more important in CS than in other (older) fields:

The answer is technological, namely airplanes. Before air travel conferences were much more difficult to attend and drew from a much more regional audience. Those who made the great effort and time to attend a conference were allowed to present. But presenting your paper at such a conference would not reach the majority of your colleagues. Journals were the most efficient way to broadly publicize your research and took on the more important role and have kept that role for historical reasons.

Computer science started as a field during the jet age. Many more people from a wider geographical base could attend a conference. One could now widely disseminate their research through conferences well before a paper appeared in a journal. Journals still played an important role for refereeing, editing and archiving but never held the importance in computer science as conferences do

Lance goes on to speculate as to what changes the internet will bring in our models of publication. It seems to me that the LANL e-print archive is one example of a new paradigm. Interestingly this has been adopted much more readily in the "old" field of physics than in computer science (as an aside, why is it that physicists always come up with cool technological developments ?), and this effect even shows up in areas like quantum computing that are on the border of the two fields.

In a sense, this is the logical evolution of the conference. If you want a place to disseminate results quickly to a wide audience, what better way to do it than via the e-print server, especially given how active it has become. Physicists still publish in journals as the primary source, but e-prints have helped replace some of the functionality of the conference.

Conferences will really never go away, since there is no replacement for direct one-on-one contact in my opinion, but e-prints are definitely a new Internet-only model...

Networking on the Network

Phil Agre has an article on networking on the internet for Ph.D Students. There are many general principles there that are quite interesting, and far too many to summarize in a brief post.

One nice excerpt:

Most people get socialized into institutions such as the research world without anyone ever explaining how the institutions work. For example, few PhD students ever get explicit lessons on the sorts of career strategies that I have been explaining in this article. What is more, the social world is filled with unspoken rules that keep these things hidden, for example the taboo against boasting or the imperative of explaining one's motives in terms of the general good rather than in terms of self-interest. These unspoken rules help people to get along, but they also make it much harder for average PhD students in complex professional interactions to figure out what is really going on. Most students do acquire up some insight from watching the experts, but they usually do not develop a complex theory like the one I have been explaining here. As a result, they often perceive their social environment in a relatively superficial way.


Pointer chase: Michael Nielsen -> Daniel Lemire -> Phil Agre.

All the above links spin off some interesting reading. In particular, Nielsen's ongoing series on the principles of effective research has some insightful thoughts.

Putnam Problem of the day...

Harvard has a Putnam Exam page that contains (apart from all the Harvard rah-rahing), a "problem of the day". Today's problem:


In Determinant Tic-Tac-Toe, Player 1 enters a 1 in an empty 3x3 matrix. Player 0 counters with a 0 in a vacant position and play continues in turn until the 3x3 matrix is completed with five 1s and four 0s. Player i wins if the determinant is iPlayer 0 wins if the determinant is 0 and Player 1 wins otherwise (thanks, Amit). Assuming optimal strategies from both players, who wins and how ?


What they need is an RSS feed. hmm....

News of the day...

Some trivial...

On the origins of 'blog', from EvHead... (via BoingBoing)

....Blog was originally devised by British fans in the 1950s. There were two versions. A Liverpool fan named Peter Hamilton came up with the recipe for Blog Mark I, which consisted of "a brandy and egg flip base, to which was added black currant puree, Alka Seltzer, and Beechan's Powder. It effervesced." A second, simplified version (Blog Mark II) was produced by hotel barmen at the first Kettering Eastercon (1955) and consisted of "a half-pint of cider and a measure of rum."
...
You'll roll down stairs, fall off your chair, and hump your neighbors dog
It goes with a snack, you'll lie on your back, it's blog, blog, BLOG!

It's blog, it's blog
It's pink, it's yummy, it's punch
It's blog, it's blog
It'll make you lose your lunch

You're gonna love your blog
Come on and get your blog
Everyone loves their blog

And some not so trivial:

From the New Scientist:

After nearly 30 years of arguing that a black hole destroys everything that falls into it, Stephen Hawking is saying he was wrong. It seems that black holes may after all allow information within them to escape. Hawking will present his latest finding at a conference in Ireland next week.

Crisis in Science ?

<Rant>
In what twisted universe does 11pt and 12 pages actually mean 10pt, illegible margins, and 20 pages ? I tell you, this is the real crisis in science.
</Rant>
Phew: now I feel better...

So this article from the Chronicle of Higher Education talks about the problems facing universities trying to admit students for graduate studies. However, even after I read it a few times, I couldn't quite figure out what its central thesis was. The subtitle says:

Leaders warn of a labor shortage in the U.S., but indicators point to an oversupply

However, the following data points are presented:

* graduate enrollment from Taiwan has dropped by 25 percent
* NSF announced that foreign enrollment reached a new peak by 2002.
* A survey of 113 schools showed a 32% drop in foreign enrollment in those schools (especially from China)
* Purdue, UCLA and UT Austin are cited as examples of foreign enrollment either going up, or number of foreign applications going up.

If you are confused at this point, join the club.

Regarding overall jobs in the market,
* BLS predicted in 2001 that there would be a 47% increase in jobs in science and engineering by 2010
* Unemployment rates in computer science and systems analysis jumped to 6.7%
* unemployment among chemists is at "an all time high", as measured in terms of the number of postdocs.

Now I am getting rather dizzy.

The article deals with a complex matter, and I can respect the need to factor in a number of different statistics, but it is not clear to me that there is any story here at all. Enrollment is going up and down, jobs are going up and down, foreigners are applying more or less: what is the conclusion ?

If we look at the summary of the article:

...although no one can predict how many scientists and engineers the nation will need in 20 years, everyone agrees that the faces of those technical leaders will be far more diverse than those of generations past, and that American universities will scour the world for the best minds.

I don't know: it seems a little wishy-washy to me...

Some detailed methodological problems:

1. There is a conflation of science vs engineering, Ph.D vs M.S vs bachelors degrees, research jobs vs non-research jobs etc. These have different dynamics, and it is dangerous to draw broad conclusions from the aggregate of so many different sectors. For one thing, unemployment in computer science may not necessarily be related to employment prospects for Ph.Ds, because the IT industry has such a huge effect on such numbers....

2. They use number of US-authored publications to indicate a "flat" trend for research in the US. Without more details, it is hard to understand this statistic. As we know from SODA/STOC/FOCS, classifying papers by country is almost meaningless in times of multi-authored papers, and in experimental fields with lots of authors/paper, even more so.

3. There is a lot of confusion over US-born student enrollment vs foreign-born student enrollment; some stats are quoted for one group, some are quoted for the total

4. Using the rate of postdoc employment to infer general trends may or may not work in general. Do people in the natural sciences go for postdocs because they can't get jobs (as was the case in theory in the early 90s), or because they NEED a postdoc to even cross the interview threshold (as appears to be true in biology at least, and maybe physics). It is possible that mathematics is an example of the first case, but I don't know if math was part of this study at all.

A point that is not made often enough:

Mr. Freeman, like other economists, looks to dollars to make sense of the trends among graduate students. "They're not studying science," he says, "because they look and say, 'Do I want to be a postdoc paid $35,000 or $40,000 at age 35, with extreme uncertainty working in somebody else's lab, and maybe getting credit for my work and maybe not getting full credit? Or would I rather be an M.B.A. and making $150,000 and hiring Ph.D.'s?'"

---

p.s So I just spent all this time writing a review of an article in the CHE instead of writing a review of a SODA submission. oh well....

The 'e' movie

No, this is not an electronic movie, it is literally, a movie about e (or a fantasy on what one would look like).

In a whimsical and interesting article on ABC News (found via topix.net), John Allen Paulos speculates on what a movie about e might look like. He was prompted by the fame achieved by the golden ratio via The Da Vinci Code, and pi via the eponymous movie.

He gives four examples of the 'natural occurrence' of e: for my amusement, I decided to subtitle the examples with the actual mathematical principle. All of these are old friends of of the theoretical computer scientist:

1. Divide up a square portion of the night sky into a very large number, N, of equal smaller squares. That is, imagine a celestial checkerboard. Then search for the N brightest stars in this portion of the sky and count how many of the N smaller squares contain none of these N brightest stars. Call this number U. (We're assuming the stars are distributed randomly so by chance some of the smaller squares will contain one or more of the brightest stars, others none.)

If one knows some probability theory, it's not hard to prove that the ratio of N to U (N divided by U, that is) is very close to e and approaches it more and more closely as N gets large.

Indeed. 1/e is the limit of the expression (1-1/n)ⁿ as n grows unboundedly large.

2. A somewhat unusual appearance of the number involves two decks of cards. Shuffle each deck thoroughly, turn over a card from each, and note if it's the same card (both 7s of diamonds, for example, or both jacks of clubs). Then turn over another card from each deck, and note if it's the same card. Continue doing this until all 52 cards in the decks are turned over. It can be shown that the probability of no matches at all between the two decks during this sequence of turnovers is extremely close to one chance in e; that is, the probability is 1/e or about 37 percent.

This is the classical derangement problem. For many of us, the first introduction to the Principle of Inclusion and Exclusion.

3. ...imagine this year's high school graduates running a quarter-mile race. Runners are randomly selected and sequentially over a period of months each of them runs a quarter-mile and we keep track of the number of record times that they establish. The first runner would surely establish a record time and perhaps the fourth runner would be faster than the first three and establish the second record time.

If the Nth runner sets the Rth record, it can be proved that the Rth root of N will be an approximation to e, and this approximation approaches e more and more closely as N increases without bound.

Another way of saying this is that if we permute a set of numbers randomly and compute the min by the standard procedure, then its value will change roughly ln n times. Timothy Chan made use of this fact in an elegant way to replace parametric search by a cheaper randomized test for many geometric problems.

The fourth example is a variant of the first: however, he alludes (possibly) to another famous homework problem, the secretary problem, in his conclusions. Here, the probability of choosing the best secretary for the job is 1/e, and this is in fact optimal (over all online algorithms that make irrevocable decisions). Considering there is already a movie called 'The Secretary', you'd think this would be a good candidate :)

As an aside, the derangement problem has also been referred to as The Drunken Secretary Problem.

If only all mathematical questions were "this complex"

Seen on CNET:

A billboard placed this week in the heart of Silicon Valley posed a complex mathematical question that most commuters on Highway 101 would need Google to crack.

So that explains why we haven't solved the burning mathematical questions of today; we didn't use Google !!

Click below to earn your $1000,000 prizes:
1. P vs NP
2. The Hodge Conjecture

For the curious, this is the "complex mathematical question":

In a kind of geek jeopardy, the billboard read:"{first 10-digit prime found in consecutive digits e}.com." The answer, 7427466391.com, would lead a puzzle-sleuth to a Web page with yet another equation to solve, with still no sign the game was hosted by Google.

Mastering that equation would lead someone to a page on Google Labs, the company's research and development department, which reads: "One thing we learned while building Google is that it's easier to find what you're looking for if it comes looking for you. What we're looking for are the best engineers in the world. And here you are.


Showing a stunning mastery of stereotypes, CNET manages to conflate eggheads, mathematicians, geeks, engineers in one horrible mish-mash.

The Importance of...: Introducing Hatch's Hit List

I try to stay out of politics, but this is just ridiculous:

The Senate is trying to pass a bill called the INDUCE Act (Inducement of Infringement of Copyright) that is as ridiculous as it sounds: one example of "inducing" infringement could be an iPod, because it encourages the use of P2P networks.

Ernest Miller has a very funny fisking of the act at corante.com. He is also maintaining a
list of devices that could become illegal under the act.

Today's burning question

From the latest issue of the Communications of the ACM:

HAS THE INTERNET BECOME INDISPENSABLE ?

In future issues:
1. DOS vs SYSTEM V: Pros and Cons.
2. Gopher: a new method for data transfer...
3. Special IBM Issue: Does the world need more than 5 computers ?

Sigh...

A dog and pony show...

Freeman Dyson has a review of Brian Greene's new book 'The Fabric of the Cosmos' in the New York Review of Books. The review provides a contrarian view on the viability of string theory, and an interesting history of the evolution of quantum physics from a revolutionary vs conservative perspective.

I found the following passage rather astounding:

Three years ago, in January 2001, I was invited to the World Economic Forum in Davos, Switzerland. Brian Greene was also invited, and we were asked to hold a public debate on the question "When will we know it all?" In other words, when will the last big problems of science be solved? The audience consisted mainly of industrial and political tycoons. Our debate was intended to entertain the tycoons, not to give them a serious scientific education. To make it more amusing, Greene was asked to take an extreme position saying "Soon," and I was asked to take an extreme position saying "Never."


Doesn't it seem sad that eminent scientists are brought out for a dog-and-pony-show in front of industrialists ? I know that "voices of reason" will argue that this is a good way to spread the Word among movers and shakers, but like this ?

---

A related article in Slate (where I found this review) also talks about the role of beauty and aesthetics in guiding (or misguiding) scientists.

SODA update

490 papers in: roughly 10% over last year (450), but then the committee is 10% larger as well :) no breakdown as yet of short vs long.

it's going to be a long summer...

SODA 2005

well the SODA submission deadline has passed (congratulations Jeff), and we have a record number of submissions this year (again). I will now go underground, to see daylight in a few months...

Apple, Wired and FOCS 2004.

Jeff Erickson snarks about Apple's discovery of the wonders of searching as-opposed-to sorting. Just to demonstrate that our community is on the cutting edge of technology trends, I present to you, hot off the presses, from the FOCS 2004 accepted papers list:

No Sorting? Better Searching!
Gianni Franceschini and Roberto Grossi

No paper link yet, alas...