Locating SODA outside the US

David Johnson forwards a note from the SODA Steering Committee about the possibility of having SODA outside the US. Summary: it can be done, with the kind of bid information that accompanies bids to other conferences with independent local arrangement. What follows is the note:

To those who might be interested in having a future SODA conference take place outside North America:

As you may know, local arrangements for SODA have to date always been handled by SIAM. The conference Department at SIAM has wide experience in organizing conferences in North America, but typically relies on help from local organizers when a conference they sponsor takes place elsewhere.

This presented difficulties when, at last January's SODA, the Business Meeting voted a preference for holding the 2011 SODA in Paris. SIAM and the SODA steering committee were unable to find any French organization that was prepared to handle the meeting in Paris. One organization might have been willing to host the meeting in the Parisian suburbs, but we judged that most of the voters for Paris would not have voted for "suburbs of Paris".

(No hotel was available in the second vote-getter, the Virgin Islands, and so SODA will be back at San Francisco, the 3rd-place choice, in 2011, January 22-25.)

In light of the experience in finding a location for the 2011 SODA, we are going to change the ground rules a bit for the 2012 site selection. Proposals of sites outside of North America will still be welcome, but to be considered, they must include the details of what group will handle local arrangements, where precisely the conference will be held, and what the expected hotel costs will be. In other words, the kind of information typically provided by groups proposing to host STOC or FOCS. (Proposals from groups that can collect registrations and take financial responsibility are preferred because of the added costs of SIAM providing these services in a country outside North America.)

If you are interested in making such a proposal at the SODA 2009 Business Meeting, please contact Kirsten Wilden (wilden@siam.org) for more details about what kinds of information SIAM will need about your proposal.

There has also been some thought that costs for SODA in North America could be reduced if local arrangements were placed in the hands of local volunteers, as they are for FOCS and STOC. If anyone wishes to propose to host SODA 2012 in this way, their detailed proposals will also be considered at the Business Meeting. (Again, contact Kirsten Wilden at SIAM in advance.)

And of course, proposals for sites that the SIAM conference staff can handle on their own can be made as usual.

Hope to see you all at SODA 2009 in Austin, January 16-19.

David Johnson, SODA Steering Committee Chair.

Anathem, and mathematical stereotypes

Neal Stephenson is (or should be !) a familiar figure in the sci-fi/speculative fiction landscape: his Cryptonomicon is a retelling of the story of Turing, along with much modern day drama involving advanced crypto and security. His new book, Anathem, came out with much fanfare, and is a vast tale set in a place where mathematics is a pursuit conducted in monastery-like places with strong religious overtones.

I'm reading Anathem right now, and am only at the beginning (so no spoilers please), but there's already a beautifully rendered discourse on stereotypes of the mathematican (or scientist in general). Inside the 'concent' (the monastery), these are termed 'Iconographies', as formal templates by which to understand how the "saecular" world perceives the mathematicians. I was reminded of this when writing I was writing the post on Soviet-style mathematics and realized the stereotypes at the heart of the referenced WSJ article.

So here are some of the iconographies discussed early on (you get one point for each one that you've encountered in real life):

• Tennestrian: seemingly clownish eccentric figures that have a darker side, luring impressionables and innocents into folly (a play on the story of Socrates)
  
• Doxan: brilliant, unemotional and cold, but as a consequence subordinate to passionate leaders with true human feeling. (can you say 'Spock'?)
• Yorran: Criminally insane mad scientist shut up in a lab with plans to conquer the world.
• Rhetorian: Sinister conspiracy plotters, out to take over the world by planting minions out in the secular world to attain positions of power.
• Muncostran: Eccentric, lovable, dishevelled theoreticians, absent-minded and good-natured (the subtext being: ignorable)
• Pendarthan: High-strung nervous meddling know-it-alls, unable to understand the realities of life, always subordinate to more 'masculine' (his words, not mine) secular folk.
• Klevan: Awesomely wise elder statesman who can solve all the problems of the world (apart from Einstein, I don't know of anyone who achieves such stature in our world)
• Baudan: Cynical frauds living in luxury at the expense of the common man (this sounds like the viewpoint of letter-writers to the Salt Lake Tribune)
• Penthabrian: keepers of mystical secrets handed down from above, with 'theory' as a smokescreen used to fool the lay folk (if only...)
• Moshianic: A combination of Klevan and Penthabrian - viewed as the most dangerous iconograph because of the high expectations placed on the theorist shoulders.

It's a neat trick to identify the ways in which the outside world perceives the 'theors', as they are called, and in doing so understand where the outsider is coming from, and what kind of threat they pose. I suspect I'm going to start classifying people in "the real world" the same way when I describe what I do.

Soviet-style mathematics

Via Anand Kulkarni (aka polybot) comes an interesting article in the WSJ by Masha Gessen on Grigori Perelman, Soviet-era mathematics and the question of 'big math'. The premise of the article (Masha Gessen has a book out on Perelman and the Poincare conjecture) is that special environments are needed to prove big results, and the Soviet-era mathematical enclaves fostered this environment both because of, and inspite of the Soviet political system.

It is indeed true that amazing work came out of the isolated confines of Soviet mathematical institutes, often parallel to or well before similar work in the Western world. There's a joke that goes around theoryCS circles that for every theorem proved before the 80s in the west, there's an equivalent result proved 10 years earlier by a Russian mathematician. We need look no further than the Cook-Levin theorem, the Koebe-Andreev-Thurston theorem (on circle packings), Kolmogorov-Chaitin-Solomonoff complexity (and according to some, the Cauchy-BUNYAKOVSKY-Schwarz inequality, though this is disputed).

But in the article is a more thought-provoking claim:

The flow is probably unstoppable by now: A promising graduate student in Moscow or St. Petersburg, unable to find a suitable academic adviser at home, is most likely to follow the trail to the U.S.

But the math culture they find in America, while less back-stabbing than that of the Soviet math establishment, is far from the meritocratic ideal that Russia's unofficial math world had taught them to expect. American math culture has intellectual rigor but also suffers from allegations of favoritism, small-time competitiveness, occasional plagiarism scandals, as well as the usual tenure battles, funding pressures and administrative chores that characterize American academic life. This culture offers the kinds of opportunities for professional communication that a Soviet mathematician could hardly have dreamed of, but it doesn't foster the sort of luxurious, timeless creative work that was typical of the Soviet math counterculture.

For example, the American model may not be able to produce a breakthrough like the proof of the Poincaré Conjecture, carried out by the St. Petersburg mathematician Grigory Perelman.

This is a reflection of one of the enduring myths of mathematical research, "a mathematician would be happy in jail if they had paper and pen", with a bit of the 'a mathematician is a solitary (and slightly crazy) genius'. I can see the allure in the idea: mathematics requires great concentration, and removal of distractions would surely make it easier to focus on a big problem.

But is this really impossible to achieve in the Western model of research ? After all, even Perelman's work built heavily on a program first outlined by Richard Hamilton from Columbia. Andrew Wiles proved Fermat's theorem while at Princeton. Ketan Mulmuley has been banging away at P vs NP while shuttling between Chicago and IIT Bombay (yes, I know it's not a perfect comparison because it hasn't been resolved yet). Stephen Cook proved that SAT is NP-Complete while at Toronto. And so on and so forth.

Possibly one argument in favor of the 'isolation: good' theory is that Perelman didn't need to prove himself for 6-7 years, maintain a steady stream of funding, and teach lots of classes in order to "earn" the right to study such a hard problem. It's hard to imagine a researcher in the US being able to do this before they get some kind of job security (tenure, or otherwise).

Innovation in Computer Science

As the polylogblogdogslogglog blog points out, the ICS results are out. 39 papers were accepted in all - at some point I knew the number of submissions, but I've forgotten since.

The ICS folks didn't make life easy for themselves by explicitly stating that they wanted "conceptual contributions". But looking over the list of papers, a few things come to mind:

• It's a great list of papers. Nothing to complain about really, and any of these could have been a credible paper at FOCS/STOC
• The Arora et al paper on designing derivatives using NP-hard problems has already received so much chatter, one might argue that the conference mandate has already been satisfied. Similarly for the quantum money followup.
  
• Even if the whole 'conceptual contributions' thing doesn't pan out, I see no harm in having a third conference inserted between FOCS and STOC - the more the merrier.
  
• I guess innovation = "game theory + crypto + quantum + misc" :)

A side note. 8 of the 12 PC members have papers at the conference. This is a departure from the theory "norm". While I don't necessarily think it's a problem (everyone except theoryCS does this, and this is also a new conference), it's worth discussing. Is this something we'd like to have happen in other theory conferences as well ? Recall that the first year of the SODA 2-page experiment also had PC-submitted papers (and that was mainly to ensure submission volume, from what I recall).

Update: Shiva Kintali has PDFs for the accepted papers.

What is computational topology ?

Jeff's post on his computational topology class (and the wonderful class outline), prompted me to write about something that I've tried to explain to people before.

Computational topology is arguably the hottest thing in SoCG-land right now, and has been so for a number of years (for curious folk, the "other" hot topic is high dimensional approximate geometry). But if you ask different people, you'll get different answers to the question "what is computational topology ?". I've even had to explain to local students why my computational geometry class is different from the computational topology class being offered. So here goes:

CT I: Using topological ideas to understand the 'shape' of data
This is the version of CT that has taken up the largest fraction of CT mindshare in the SoCG land. Dating back to work by Edelsbrunner and Mucke on alpha-shapes, the field now encompasses a range of ideas for extracting topological structure from data. New topological constructs that have come from this area include various notions of persistence, as well as related work on reconstruction, data smoothing, and visualization.

Afra Zomorodian's thesis (now a book) is a nice introduction to these concepts for a CS audience. Herbert Edelsbrunner is coming out with a book on this topic very soon (Jan 16, 2010! Mark your amazons!), and Valerio Pascucci teaches a class on computational topology at the U.

CT II: Asking computational questions about fundamental topological objects and concepts.
This is closest to the 'Computational X' flavor of work, where a computational perspective is brought to the study of X. There are many interesting problems here, and they have a nice discrete flavor that makes them 'friendly' for theoryCS folk. For example, computing the Betti numbers of a simplicial complex efficiently, or finding homotopy equivalent paths on a surface, or lots of work on graphs on surfaces.

I don't think there's a single book on this topic. JeffE has put together a fantastic course outline (with reading material), and there's also a great book on graphs on surfaces by Mohar and Thomasson. It's worth noting that some of the deeper tools in the Robertson-Seymour graph minor results take us into graphs-on-surfaces-of-large-genus land.

CT III: Using topological ideas in the heart of complexity theory.
Almost no one I know uses 'computational topology' in this sense, and there isn't a coherent and connected body of work to talk about as such. But there are some fascinating results at the core of complexity theory that rely on topological constructions. There's the algebraic complexity work of Yao/Steele/Ben-Or and others, showing that lower bounds for algebraic complexity of certain problems can be related to the sum of Betti numbers of associated surfaces. There's the Kahn-Saks-Sturtevant (and Chakrabarti-Khot-Shi) work on evasiveness of graph properties, and then the work (that I don't quite understand) on topology in distributed computing (that got Herlihy, Saks, Shavit and Zahoroglou the Godel Prize)

This is one of the reasons I think a course in topology (of some flavor, whether it be combinatorial, algebraic or point-set) should be required mathematical background for all theoryCS students.