FOCS/STOC Reviewing

Bill Gasarch has a long list of questions about paper review processes at FOCS/STOC (what happened to SODA?) following up on Vijay Vazirani's not-radical-enough guest post about submitting videos along with submissions. Since it's tedious to post a list of answers to so many questions in comments, I'll post it here, and let Blogger trackback work its magic.

1. Is the community really driven by these conferences? An Underlying assumption of these discussions has been that someone judges us based on the number of STOC/FOCSs we have. Who is this mysterious someone? Is it our departments? Our Colleges? Ourselves? Granting agencies?
   
   Well it's not really that mysterious: I'd say all of the above.
   


2. Is it bad that we are so judged?? PRO: Its good to have a central place where you know the good papers are. CON: The rest of the items on this list are about what problems there are in judging quality CON: Some of these papers are never put into proper journal form. CAVEAT: Is the Journal-Refereeing system all that good to decry that it is lacking here?
   
   Nothing wrong with being judged. However, the assumption that FOCS/STOC is the repository of all "good papers" is problematic. And personally, I'm tired of people complaining all the time about journal refereeing. The SAME people who review papers cursorily for conferences are the ones who do it for journals. If conference reviewing is "OK", what makes journal refereeing so terrible?
   


3. Other fields do not have high-prestige conferences- why do we and is it a good thing?. Our field moves fast so we want to get results out fast. It is not clear that FOCS/STOC really do this. Using the web and/or Blogs can get the word out. Important new results in theory get around without benefit of conferences. For results just below that threshold its harder to say.
   
   I'm sorry. I'm having a hard time getting through the fog of hubris around this statement. I fail to understand how we can have the gall to stand up and say that CS theory moves a lot faster than any field that abjures conferences. Bio journals publish every few weeks, and there are mountains of papers that show up. For a closer-to-home example of the herd mentality that often drives research in theoryCS, papers in string theory appear at high rates without needing the acceleration of conferences.
   


4. Are the papers mostly good?
   
   As I was saying to someone the other day, it's unlikely that you'll find more than a couple bad FOCS/STOC papers in each proceedings. So, Yes.
   


5. Is their a Name-School-bias? Is their a Name-person-bias? Some have suggested anonymous submissions to cure this problem.
   
   After a recent SODA, someone levelled this complaint against the committee, both in terms of committee composition, as well as paper acceptance. There is some info on this matter here.
   


6. Is their an area-bias? There are several questions here: (1) is the list-of-topics on the conference annoucement leaving off important parts of theory? (2) is the committee even obeying the list as is? (3) have some areas just stopped submitting?
   
   I'd argue that there is (mostly) faddism rather than bias; certain topics gain a certain cachet in certain years, and often papers that in other years might not have cracked a FOCS/STOC list do so. However, (3) is definitely true to a degree for computational geometry and data structures. I've lost count of the number of people who claim that they only submit to STOC/FOCS because of tenure pressure. It's not clear to me whether actions match words in this regard, but the prevailing sentiment, at least in these two areas, is strong.
   


7. Is their a Hot-area-bias?
   
   YES: see above.
8. Is their a mafia that controls which topics gets in?
   
   I've never been on a FOCS/STOC committee, but I'd strongly doubt this. I think our community is full of strong personalities, and it's hard to imagine that many people working together with such cohesion :)
   


9. Is their a bias towards people who can sell themselves better? To people that can write well?
   
   Undoubtedly so. However, this cannot be viewed as a problem per se. It's just a function of human nature; if you understand something better, or it seems clearer, you will often view it favorably. And there's nothing wrong in creating an evolutionary pressure towards better writing and "framing"
   
10. Is their a bias towards making progress on old problems rather than starting work on new problems?
    Not really. I think there's a mix of preferences, and that reflects individual interests.
    
    
11. Is their a bias towards novel or hard techniques?
    
    Again, I suspect people have their own viewpoints; some like beautiful proofs, some like novel techniques, some are impressed by technical wizardry , and so on.
    
12. Is it just Random? Aside from the clearly good and clearly bad papers, is it random? Is even determining clearly good and clearly bad also random? One suggestion is to make it pseudo-random by using the NW-type generators. This solves the problem in that since it really is random it is less prestigous and most of the problems on this list go away. Would also save time and effort since you would not need a program committee.
    
    Well since the vast majority of submissions to any conference are in the mushy middle, we have to invoke the proposition that I think is attributed to Baruch Awerbuch: the probability of a paper being accepted is a random variable whose expectation is a function of the paper quality, and whose variance is a function of the program committee.
    
13. Are there many very good papers that do not get in? It has been suggested that we go to double sessions so that more get in. If the quality of papers has been going up over time this might make sense and would not dilute quality.
    
    This goes back to the dual conflicting roles of a conference: quality stamping and dissemination. You will almost certainly dilute the first by increasing paper acceptances, but you will only help the second.
    
    
14. Is 10 pages too short for submissions? This was part of Vijay's Video Suggestion. Are figures and diagrams counted for those 10 pages? If they are they shouldn't be.
    
    Too short for what ? Reviewers, with the number of papers they need to review, can hardly be expected to read 20 page submissions. And as an aside, if you can spend the time on a video review to explain the paper, why can't you use the same time to write a GOOD outline of the main ideas in one section of the paper itself ?
    
    
15. Are many submissions written at the last minute and hence badly written?
    
    YES
16. Are many submissions written by the authors taking whatever they have by the deadline and shoving it into a paper?
    
    OFTEN
17. Since the conference is about all of theory, can any committee do a good job?Vijay was partially addressing this problem by trying to find a way to make their job easier.
    
    Committees try, with extensive outsourcing, but it's essentially an impossible task, and one should not expect perfection.
    
18. Do other conferences have these problems? That is, the more specialized conferences- do they have similar problems? Why or why not?
    
    Allowing PC members to submit changes the review dynamics tremendously. It increases the reviewer pool, reduces reviewer load, but also reduces the quality of review ratings. Most other communities allow PC submissions, so it's really hard to compare. I am NOT advocating going this route.
    
19. Do you actually get that much out of the talks? If not then it is still valuable to to go for the people you meet in the hallways?
    
    Schmoozing is much more effective for me than attending talks. But that's just me. Others may have different viewpoints.
    
20. For all the items above, even if true, are they bad? Some have suggested that bias towards big-names is okay.
    
    Bias towards "big-names" is braindead. Bias towards quality is perfectly fine. A correlation between "big-names" and quality does not imply that one should be replaced by the other.
    

On judgements

Paul Graham has a short note on judgements which seems apropos to dealing with rejection of various kinds (papers, jobs, grants, etc):

Our early training and our self-centeredness combine to make us believe that every judgement of us is about us. In fact most aren't. This is a rare case where being less self-centered will make people more confident. Once you realize how little most people judging you care about judging you accurately—once you realize that because of the normal distribution of most applicant pools, it matters least to judge accurately in precisely the cases where judgement has the most effect—you won't take rejection so personally.

Factoidals

Brian Hayes has a very interesting article in American Scientist on the 'factoidal', a stochastic version of the factorial that he coined. It's defined as follows: for input n, pick numbers at random between 1 and n, multiplying them together until you pick a 1.

He expands at some length on the stochastic properties of this function: unsurprisingly, the arithmetic mean of samples of this function doesn't converge with more samples, but the geometric mean does. What's a little more surprising is that the distribution isn't log-normal. One might expect that since upon taking logs, we're averaging a collection of random numbers between 1 and log n, we might expect the average of the logs to display normality, but that doesn't happen.

The explanation is a nice take-way nugget from this article. In short, work by William Reed and Barry Hughes from 2002 shows (this example taken from their abstract) that if you take an exponentially growing process (for example ), and truncate it at a random time given by an exponential process (for example, with parameter ), then the resulting random variable exhibits the power law distribution

Latex For Blogger

This is a neat plugin. And just to test it, here's the Johnson-Lindenstrauss Lemma:

For any and any integer n, let be a positive integer such that

Then for any set of points of n points in , there exists a map such that for all ,

Not bad at all !

Knuth Prize

Nancy Lynch from MIT has been awarded this (one and half) year's Knuth Prize for her work in reliability of distributed computing. I remember first hearing about her work when I studied distributed computing and Byzantine agreement problems back in IITK.

This has been a good (and well deserved) year for women in computing: first Frances Allen, and now Nancy Lynch.

The Cauchy-BUNYAKOVSKY-Schwarz inequality

Episode #2583 of "By the law of large numbers (of Russian mathematicians), your theorem has been proved by some Russian before you even thought of it":

Viktor Bunyakovsky worked on Number Theory as well as geometry, mechanics and hydrostatics. He discovered the Cauchy-Schwarz inequality 25 years before Cauchy or Schwarz.

Measure concentration

I've been preparing a lecture on the Johnson-Lindenstrauss Lemma and dove deep into the beautiful world of measure concentration. Matousek's chapter on the topic is excellent in this regard, but I found that the flow of the results (from measure concentration towards the JL Lemma) was not to my taste either personally or pedagogically (it's possible to discuss the lemma algorithmically using elementary proofs without having to uncover the deep measure concentration machinery chugging below).

In that respect, Alexander Barvinok's lecture notes on measure concentration prove to be quite useful. He starts from simple measure concentration on the sphere, builds up to the JL Lemma, and then carries on forward into Levy's theorem, Dvoretsky's theorem and the Brunn-Minkowsky inequality. He starts with a good intuitive definition of measure concentration:

Any "reasonable" function defined on a "large" probability space takes values close to its average with high probability

which nicely ties it together (in my mind) with other large deviation results in information theory as well (he also has a section on rate distortion and Cramer's work).

Another useful nugged from Barvinok's notes is a thorough drilling on the use of the "Laplace trick": the technique of taking the exponential of a random variable and applying the Markov inequality in order to prove tail bounds (the standard proof of the Chernoff bound is one example of this).

Inventor of 'idf' passes on

Karen Sparck-Jones, professor at Cambridge University, winner of the Lovelace Medal and the Allen Newell Award (among other awards), died today. She was a pioneer in NLP and information retrieval, and is also the inventor of one of the most fundamental notions in information retrieval: the concept of IDF (or inverse document frequency).

Information retrieval methods are at the heart of web search today, even in the age of link structures and PageRank. One of the most elementary and yet most enduring ideas in information retrieval is the concept of a document as a "bag of words"; namely that even if we encoded a document as a (weighted) set of terms occuring in it, we can extract meaningful information from it. The 'bag-of-words' model itself dates back to at least to Gerald Salton's IR book in 1968; it is probably much older.

Once you think of documents as bags of "terms", you need a way of weighting these terms in a way that allows "similar" documents to have a similar set of weights. Term frequency (TF) is one way of doing this: weight a term with a number proportional to how often it appears. This makes some sense; a document about soccer might use the word 'football' or 'soccer' fairly often, as compared with a document on cricket.

However, words like 'a', 'an' and 'the' also appear very often in a document. How does one prevent these terms from washing away any semantic context one might have ? One idea is to weight the term frequency by something called 'Inverse Document Frequency' (IDF). For a given collection of documents, count in how many documents a fixed term appears. This number is the term's document frequency. Clearly, a term that appears in all documents can't be a useful distinguisher of a document and so the larger this number is, the less relevant the term. Therefore, by multiplying the term frequency by a function inversely related to the document frequency (if p is the fraction of documents a term appears in, the IDF is often set equal to log(1/p)), you get a more accurate estimate of the importance of the term.

This to me is a very modern way of dealing with documents, and yet the idea itself was proposed by Karen Sparck-Jones back in 1972, well before we could imagine search engines, and fast computers that could crunch these numbers in a jiffy. I'm not an expert on IR methods, but I dare say that a simple TF-IDF computation is, even today, a first preprocessing step when organizing document collections.

(Via Hal Daume)

Generalized(?) Dyck Paths

A Dyck path is a useful metaphor for dealing with Catalan numbers. Suppose you are walking on an n X n grid, starting at (0,0). You can make a horizontal move to the right or a vertical move upwards. A Dyck path is a path in this grid where

• the path ends at (n,n)
• the path may touch (but never goes over) the main diagonal

The number of Dyck paths is precisely the Catalan number C_n-1. One way of seeing this is that all Dyck paths that touch the diagonal at some interior point can be written as the concatenation of two Dyck paths of shorter length (one from the origin to the point, and one from the point to (n,n)). Dyck paths are also related to counting binary trees, and strings of balanced parentheses (called Dyck languages).

People have studied "generalized" Dyck paths, where the grid is now rectangular (n X m), and the step lengths are appropriately skewed. However, what I'm interested in is the following seemingly simple generalization:

Let a (n,k)-Dyck path be a Dyck path with the modification that the path, instead of ending at (n,n), ends at (n,k) (k <=n). What is the number of (n,k)-Dyck paths ?

It seems like this should have been looked at, but I've been unable so far to find any reference to such a structure. I was wondering if readers had any pointers ? Note that this number is at most C_n-1 since any such path can be completed into a unique Dyck path.

Visiting JPL

I'm at JPL today and tomorrow, visiting a colleague (and hopefully collaborator) at NASA, and attending the first day of the AIRS Science Meeting.

AIRS stands for the Atmospheric Infrared Sensor, an instrument that sits aboard NASA's Aqua satellite. Along with other sensors onboard Aqua, AIRS provides for detailed atmospheric sensing, especially of greenhouse gases that account for climate change.

In fact, the AIRS science meeting is ground central for some of the climate change work that we mostly hear about through a political lens. It's fascinating to sit in the JPL cafeteria and listen to atmosphere scientists talk about some of the fundamental problems in climate science (clouds are apparently a BIG mystery in terms of how they influence global temperature).

So what's a computer scientist doing in this super-charged atmosphere ? The instrument produces gargantuan amounts of data, and there are all kinds of interesting data analysis questions that need to be addressed at scale. What makes these questions interesting is that unlike in much of mining, there is a physical ground truth that we can use to validate any interesting patterns that a mining process might uncover.

An ending...

They say, "all good things come to an end". What they don't say is, "if good things didn't end, you wouldn't realize how good they were".

Lance announces today that he's shutting down the Computational Complexity blog. As far as I know, he's the ur-TCS blogger, and was the direct inspiration for my starting the Geomblog. I've always had the Complexity blog on my must-read list, and have felt both pressured (to write better posts) and inspired (by the rich content) every time I've seen a new posting.

Another aspect of Lance's blog that I envy is the rich commenter community: he was able to create a forum for discussion of TheoryCS, on matters both technical and non-technical, that will be hard to replace.

So thanks for all the posts, Lance, and hopefully you'll be back one day !

4th Carnival of mathematics up

Read all about it.

Job announcements

For people who don't subscribe to compgeom-announce:

• [Apr 30 deadline] One-year postdoc in the area of computational geometry and topology, @ GIPSA laboratory, CNRS - UMR
• [Apr 30 deadline] Ph.D position in INRIA in computational geometry, specifically on triangulations for non-standard geometric spaces.
  

Meta-posts

I was browsing my referrer logs and found a callback to Lance's blog. In the comments for the post, I see this comment (emphasis mine):

Here's one that I've found very vexing: Let A(d) denote the least surface area of a cell that tiles R^d via the translations in Z^d. Improve on the following bounds:

sqrt(pi e / 2) sqrt(d) <= A(d)/2 <= d - exp(-Omega(d log d)).

(It's a little more natural to consider A(d)/2 than A(d).)

The lower bound is by considering a volume-1 sphere, the upper bound by monkeying around a little with a cube's corner.

Any proof of A(d)/2 >= 10sqrt(d) or A(d)/2 <= d/10 would be very interesting.

For motivation: Either pretend I posted on Suresh's blog (so it's just a problem in geometry); or -- it's related to finding the best rate for parallel repetition of a simple family of 2P1R games.

It's a meta post !!! And by the way, there's no such thing as "JUST a problem in geometry". Harumph !!

;)

On ranking journals

Via Cosma Shalizi comes a new way of ranking journals developed by Jevin West, Ben Althouse, Martin Rosvall, Ted Bergstrom, and Carl Bergstrom. It works on the PageRank principle: take a random paper from a journal and do a random walk on the citations, using the stationary distribution to rank journals. The result is eigenfactor.org, a website that catalogues many journals and other publications, and provides both a ranking by their "pagerank" but also a "value for money" that might be useful when deciding which journals to purchase for a library.

Impact measurement for journals has become a popular parlor game, as well as impact factors like the 'h-index' for individual researchers. There are all kinds of problems with these measurements in general, and Eigenfactor does provide a way of eliminating some of the usual problems with measuring impact across multiple communities with different citation mechanisms, community sizes, and so on.

Eigenfactor has a few top 10 lists for different areas (science, social science, etc): here's my informal list of top ranked computer science algorithms (and friends) journals, ranked by article impact factor (all scores are percentiles over the universe of 6000+ journals considered):

• SIAM Review: 98.35
• J. ACM: 97.91
• IEEE Trans. Inf. Theory: 95.05
• Machine Learning: 93.92
• SICOMP: 93.04
• JCSS: 90.93
• Journal of Algorithms: 90.31*
• DCG: 85.29
• CGTA: 81.96
• Algorithmica: 79.13

* The ACM Transactions on Algorithms, which absorbed most of the editorial board of J. Alg, is too new to show up. This ranking should probably reflect the historical relevance of J. Alg as well as its current state.

John Backus, 1924-2007

John Backus died on Saturday. He was the father of FORTRAN, Turing Award winner, and one of the names behind the Backus-Naur form (Peter Naur, 2005 Turing Award winner, was the other).

No matter how much you might make fun of FORTRAN today, the fact is that it remains the language of choice for many scientific computing packages. Even if you're writing in C, you're probably interfacing with routines first written in FORTRAN.

His Turing Award lecture is also a remarkable read. Titled, "Can programming be liberated from the Von Neumann style", it laid the groundwork for functional programming, and anticipated many of the stream programming paradigms that we see today, from GPU programs to Google's MapReduce system. I'm always humbled when I read articles from so many years ago that have such resonance today; I can only hope that anything that I do can still have value even ten years later.

Anonymizing PDF

File this under 'late-night LaTeX griping':

Is there any way of stripping metadata from a PDF file ? I'm writing a referee report for a journal, and used PDFLaTeX to create the report. When I scan it in acroread, there's all kinds of meta data that could identify me.

Now pdftk is a useful package that can strip out some of the simple metadata like 'creator'. However, pdftex adds "Advanced" fields, and one of them is the full pathname of the original LaTeX file. If your filesystem (UNIX) is anything like mine, then a part of that pathname is the /<username>/ section, which in many instances is an almost unique identifier. This also happens with dvipdfm, which uses the gs backend to create the PDF file, and with ps2pdf. pdftk cannot strip out these fields, because it doesn't appear to see them.

I suspect that if I owned a copy of the very-not-free Acrobat, I could meddle around with this metadata. Obviously I could submit the review as a Postscript file, but in general I prefer to maintain PDF. Further this problem also occurs if I want to do due diligence when submitting to conferences with double blind review, and sometimes I don't have the option to use PS.

Dr. Karp and The TCS Lens

or How I learned to stop worrying and love complexity.

[ed. note: This note was prompted by Aaron Clauset's series of articles titled 'Unreasonable effectiveness' (the title itself a riff on Eugene Wigner's famous essay). Further inspiration came from reading the various summaries of Karp's 'algorithmic lens' idea.]

I believe in the gospel of St. Bernard. We are about to enter the age of the algorithm. The only question is: what kind of algorithm will it be ?

We're all familiar with the steps. Define the problem. Design an algorithm. Analyze the algorithm. Rinse and repeat, till we have a matching lower bound, or till we hit an even harder problem. Algorithms are designed from the top down, by a coffee-swilling researcher with a whiteboard, with the elegance of a swiss watch, or the clumsiness of a sledgehammer. Some of them are so beautiful they make you weep. Some are algorithms "in name only"; no one in their right minds would ever dream of implementing one of these beasts.

The algorithmic lens flips this on its head: complexity (and the solution) emerges from a set of simple rules. It's like Spore; set up the rules, start the game, and see what happens. The ingenuity here is not in the construction of a solution, but in the design of the rules. It's declarative, not procedural. It's bottom up, not top down. It's distributed, not centralized.

It has the flavor of (computational) complexity: I'll give you a resource; a guess, a random coin, a scratch pad, an AskJeeves clone. You tell me what I can do with how little. But it's still a lens. Why ? Things we're familiar with show up as distributed, bottom up, emergent constructions: A Voronoi diagram is a battle between equally (or unequally) matched forces. A Steiner tree is a soap bubble diagram. A clustering algorithm is a local "I'll go to my closest friend"; a regular language is the consequence of amnesiac entities bouncing around between states.

It's unsettling: we aren't the masters of our domain any more. We're not GOD, intelligently designing beautiful watches. We're just the rule-makers for a complex system. It's like being the parent of a young child !

What we can do is this: find out which rules yield cause what solutions to emerge. We study social networks, and watch complexity emerge from a set of simple pairwise interactions. In other words, the algorithm IS the social network. You can't get much more Web 2.0 than that...

If you've heard this before, it's because you have: things like the Ising model, phase transitions, statistical mechanics, Conway's Game of Life, Stephen Wolfram's New Kind of Science. So what makes these concepts so exciting now ?

Maybe it's all about scale. We preach that immense scale requires theoretical analysis; the N0 in the "for all n > N0" of O() notation is finally here. But maybe linear time algorithms, streaming algorithms, and small space sketching are all soon-to-be-futile attempts to stave off the inevitable horrible failure of programs to manage the complexity of the data we deal with. Suddenly, local algorithms that evolve continuing solutions look quite appealing, as well adaptive.

It's an exciting time to do algorithms, whether you're designing watches, or setting up an ecosystem.

A movie about a font is my kind of movie

One of the curses of making web pages and writing documents is an unhealthy obsession with fonts. People who've written papers with me have heard my paens to the Euler math font with barely suppressed irritation, and I often have to stop myself from attempting to call out names of familiar fonts when walking down the street :).

Sounds like this is the movie for me:

Helvetica, which had its world premiere at the conference, presents the life story of something all of us encounter on a daily (or even hourly) basis. Created in 1957 by the Swiss modernist designer Max Miedinger as a response to the cluttered typography and design of the postwar era, Helvetica's clean neutrality and balanced use of the empty space surrounding letters quickly made it a go-to font for public signage, advertising, corporate logos and works of modernist design around the world

[...]

Filmmaker Gary Hustwitt revels in his fascination with something so commonplace that it blends almost entirely into a context-less background, becoming a detective of sorts to unveil the myriad everyday places Helvetica is hiding (“It's a disease,” Hustwitt said of his obsessive font-spotting).

And he's OOOUUUTTT !!!!

Yep, the world cup is now finally on. After a long time, I'm in the same time zone, which is not as nice as it might seem, given that all matches are during the workday. I was trying to explain this to my wife, and she said, 'Aren't cricket matches always at 3 am ?'. Considering that the last time she saw cricket was when I dragged her out to see the India-Aus final 4 years ago, she has a point :).

As people who watch cricket in the US know, Kelly Broadcasting has had a strangehold over cricket rights in North America for some time now. This year however, there are many more options for watching cricket. You can continue to watch the WC on dishTV, but now DirecTV has moved into the biz with a $200 package for the entire cup. If that's too pricey for your taste (and you can't spend all day at home watching on TV!), then sgstream.com has a streaming package for $75, which to my amazement works quite well (so far; let's see what happens for the first India game).

Right now, WI is 140-3 after 36 overs against Pakistan.

Order polytopes

One view of the techniques of computational (and combinatorial) geometry is the delicate tension between the discrete (combinatorial) and the continuous (geometric). Whether it be Davenport-Schinzel sequences and lower envelopes, or VC-dimension and intersections of geometric sets, a common step in making geometric structures tractable is finding a combinatorial structure that captures the aspect of the geometry that's important for a particular problem.

It's nice to return the favor sometimes. Combinatorics and topology have strong connections, and one doesn't have to go too far from home find instances of "lifting" a combinatorial problem to a topological domain to solve it; Lovasz's proof of the Kneser conjecture, and the various methods for proving evasiveness properties, are among the more well known examples. In fact, distributed computing is replete with topological hammers for proving properties of protocols.

Of course, one can view the entirety of linear programming as an example of lifting combinatorics to geometry; I'm deliberately ignoring it because you have to go through the integer lattice to get combinatorial problems, rather than having geometry characterizing the structure directly. This is of course totally ad hoc :)

What I describe next is an extremely elegant geometric view of a purely combinatorial problem. Suppose you're sorting numbers, and you have some rough idea of the sorted order. Maybe you can rank some of the elements, but not all of them (for example, maybe you're integrating results from different web searches). At any rate, what you have is a partial order, and you'd like to get a sense of its 'orderedness'. Specifically, you'd like to estimate the number of different ways this partial order can be completed (by inserting orderings between as-yet unordered elements without disturbing existing order). Such a completion (or extension) is called a linear extension, because you can think of the final total order as being points on a line, numbered from lowest to highest rank.

For example, suppose you have the four elements (a,b,c,d) and you know that (a < b) and (c < d). There are then six ways of constructing a linear extension from this partial order.

Suppose now that comparisons were costly, and we'd like to choose the next comparison so as to reduce the number of potential linear extensions by as much as possible. If we could guarantee that the number reduced by an α fraction, then we could complete the sorting using log_α E comparisons, where E was the number of linear extensions to begin with. Since each comparison partitions the set of linear extensions into two sets, clearly this fraction must be at least 1-α.

It's not hard to see that we can't do better than α = 2/3, by considering the partial order {(a < b), c}. There's always a way of picking the answer to the next comparison to make this so. The best known bound to date is roughly α = 0.7236, and this bound (and earlier methods) make use of an elegant geometric characterization of linear extensions via order polytopes.

Given n elements in the partial order, let the order polytope be the set of points in [0,1]ⁿ such that the coordinates of each point satisfies the partial order. Namely, if there's a constraint of the form a₁ < a₂, then the coordinates x₁ and x₂ of the point x satisfy the same constraint.

It's not hard to see that this is indeed a polytope; it's the intersection of a set of hyperplanes, and is bounded. What is more intriguing is that every simplex of this polytope corresponds to a specific linear extension. If we look for example at the simplex defined by the four blue points, the coordinates are (0,0,0), (0,1,1), (0,1,0), and (1,1,1), which describes the order (a < c < b). All these simplices are congruent and non overlapping, and each has volume 1/n!. This implies the remarkable result that the number of linear extensions for a given partial order is the volume of the resulting order polytope, divided by n!.

The favor gets returned as well. The paper, "Counting linear extensions is #P-complete", by Brightwell and Winkler in 1991, yields the corollary that computing the volume of a polyhedron is #P-complete.

For more on this, Matousek's Lectures on Discrete Geometry is a wonderfully readable source.

Computer Scientist:Programming::Mathematician:Arithmetic

One of the things that continues to exasperate me on a regular basis is the conflation of computer science with programming. Consider two recent gems (emphasis mine):

1. From a press release for Microsoft TechFest 2007:

   Boku, a virtual robot in a simulated world, debuted as a research project to teach kids basic programming skills in a fun and entertaining way. “There is an ongoing and deepening crisis in computer science,” Rashid said. “Our goal is to stem the tide by showing young kids the magic of software programming.”

2. From an article on changing perceptions of computer science at college and K-12 level:

   East Allen County Schools is working to make sure students are exposed to computer careers, whether they think they might be interested or not. All students are required to take a computer course before graduating, and those who know they are interested can take in-depth courses, including training on Cisco computer networks...

Sigh. Ok people, say after me, slowly: Computer Science IS NOT programming. How many musicians do you think you're going to attract by preaching the exquisite beauty of scales and arpeggios to little kids?

As Lance mentions, the closure of stores like CompUSA is a harbinger of the end of computer science as "television science". The more familiar people get with computers, the more they treat them as appliances rather than as complex devices worthy of worship.

What does this mean ? You aren't going to attract people to a field by saying, "Lookee here! here's a neat television ! Let me show you how to build one. It's FUN!!!!". First of all, people ain't stupid. Secondly, there's a lot more to computer science than programming.

Thankfully, we do see here and there the signs of a manifesto for computer science that doesn't involve actually programming a computer: From Jeanette Wing's CACM article:

Computer science is the study of computation: what can be computed and how to compute it.

Amen to that. And notice how different it sounds to the version you might get from the random person on the street:

Computer science is the study of computers.

If I had to preach the gospel of computer-science-as-computation, I'd probably riff off three things:

• The above mentioned CACM article. Message: Computer science is the study of algorithms and abstractions.
• Bernard Chazelle's IPod essay. Message: Algorithms are the language of modern science
  
• Scott Aaronson's 'Logicians on Safari' article. Message: Computer science is quantitative epistemology.
  

'Nuff said.

p.s Chazelle is quickly becoming the poet-laureate for 21st century computer science: check out the table of contents for his course titled, "What do your DNA and your iPod have in common ?"

Simulacrums all the way down...

You can already meet politicians, autograph books, have all kinds of kinky virtual sex, and complain about virtual denizens who spend their time in their virtual houses playing virtual video games. And now you can even get pregnant, virtually speaking (this from the creater of Fable, an Xbox RPG):

“There is the appreciation the wide world feels toward your character as he lives and fights in their world. There is the ability to make love and make babies. Yes, you can be both a man or a woman and if you're a woman, you can get pregnant. A first, he believes, for a main character in an RPG.”

(HT: Penny-arcade)

So so true....

From xkcd, the only geek comic you need ever read:

Dating a result..

The PCP results appeared in conferences in 1992, Sanjeev Arora's thesis appeared sometime after, and the "journal version" appeared in 1998. Similarly, the PRIMES in P result was announced in 2002, but was published in the Annals of Math in 2004.

If I'm trying to write something that talks about the history of a set of results (let's say I'm talking about PCP), it is generally recommended that I cite the definitive version (i.e the journal paper). So I'd talk about a PCP result "published in 1998", which seems silly given that everyone knows it appears much earlier. Given the lag time of CS journals, this is more of a problem than in other areas.

Is there any clean way out of this dilemma ? Should I cite the journal, but attempt to avoid any mention of dates in the text ? Should I use the "first published date" in the text, and cite both the earlier, conference version, AND the journal version ?

Maybe it doesn't matter, because the only results worth announcing well before publication are so famous that such questions are moot, and "everyone knows when it appeared". I don't have answers here: I'm just confused.

Presidential candidate wants to repeal undecidability.

From CNET, via BB, and Ed Felten:

Sen. Sam Brownback (R-Kansas) on Tuesday reintroduced the Truth in Video Game Rating Act, first proposed last September. It calls for requiring video game rating organizations to play all games "in their entirety" before issuing labels and prohibiting game developers from withholding any "hidden" game content from raters. It would also punish ratings groups that "grossly mischaracterize" any game's content.

That's right: he wants to have games played till they terminate, in order to have them certified. I guess it's time to dust off those "Pi = 22/7" legislations.

Fran Allen, Turing Award, 2006

Fran Allen, Fellow Emerita at IBM, has been named this year's Turing Award winner. She is also the first woman to win this award.

WADS deadline fast approaching

For those of you nursing your poor SoCG/STOC/PODS rejects, the WADS deadline is fast approaching. WADS (The Workshop on Algorithms and Data Structures) alternates annually with SWAT, the Scandinavian Workshop on Algorithm Theory, and is being held this year in Halifax, Canada. Lest the title fool you, WADS is actually an honest-to-goodness conference; proceedings are published in an LNCS issue.

The deadline is Feb 23, more than enough time to even invent a problem, solve it, write a snappy intro, and send it off. So get cracking !

Update: The deadline has been moved to Mar 2. Heck, you could write TWO papers in that time.

p.s Not that the WADS folks are asking for my opinion, but I don't like it when conferences shift deadlines.

STOC 2007 Results out

Via Piotr, the STOC 2007 results are out. They are sneakily hidden on Uri Feige's home page, so if you go to the STOC page, you don't see them.

77 papers made it in: I don't know how many were submitted (Update: 312, quite a healthy number). As is often with STOC, the titles are somewhat inscrutable, so it's hard to spot papers that might be interesting.

Some notable entries:

• Computing crossing number in linear time, by Ken-ichi Kawarabayashi and Bruce Reed:

  For a fixed k, they determine whether a graph can be drawn with crossing number at most k, and if so, construct such a drawing, all in time linear in n. This improves an earlier quadratic time algorithm of Grohe.
  

• Combinatorial Complexity in o-Minimal Geometry, by Saugata Basu.

  A continuation of his work on estimating complexity of various topological quantities, for even more generally defined subsets of Rⁿ.

• Fourier meets Möbius: fast subset convolution, by Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto.

  An application of the Möbius transform, in a kind of generalization of the use of Fourier transforms, but for subset convolutions.

• Lower Bounds for Randomized Read/Write Stream Algorithms, by Paul Beame, T. S. Jayram and Atri Rudra.

  This is another in a series of papers that I really must read, given how it reminds me of things I was dabbling in involving graphics cards. The quirk of this model is that the stream algorithm can write onto streams as well as reading from them; memory is limited, but not intermediate storage (for writing such streams)

Parochial concerns section: by my count, 6 geometry papers, which is fairly decent.

Fastlane and Holidays

As many of you are painfully aware, the NSF deadline for theory proposals is this Monday, Feb 19. As you may have also realized, Feb 19 is a federal holiday. According to NSF guidelines, in such an event, the deadline moves to the next working day (i.e the 20th) and I've confirmed that this is a correct interpretation for this deadline.

However, does Fastlane itself know this ? Suppose Fastlane refuses to accept any proposal submitted after Feb 19 (since in principle it has the information on the call and the deadline) ? Can the program manager then override it ?

I wonder if anyone has any experience with this...

Valentines for my current state...

• XEmacs, AUCTeX and RefTex
• The pre-coded BibTeX at the ACM DL and DBLP
• Pandora.com

New Research Center in Massive Data Algorithmics

Lars Arge, crown prince of massive data set algorithms, informs me that MADALGO, a new research center devoted to massive data algorithmics, is now up and running.

Several Postdoctoral positions at the level of Research Assistant Professor of Computer Science are available. Initially, the positions are for one year, but they can be extended by mutual consent. Applications are welcomed from researchers with clearly demonstrated experience and skills in the design and analysis of algorithms and data structures. Applicants with experience with I/O-efficient, cache-oblivious or streaming algorithms, as well as with implementation of such algorithms (algorithm engineering experience), will be preferred. The responsibilities of the candidates include work on algorithms for massive dataset problems in collaboration with center researchers, along with modest teaching responsibilities.

It's a great opportunity if you're looking for somewhere to do a postdoc, and like mucking around with lots of data. Massive data problems have added a profound new dimension to algorithms research, and this center will really help push research in this area forward. There are also Ph.D student positions available.

Weird BibTeX problem

This is puzzling me, and I am hoping my readers might help:

I want to add a reference to this entry:

@article{ref,
author = {First Last and First M. Last, III},
title = {Insert Title Here},
journal = {Int. J. Comput. Sci.},
volume = 1,
number = 1,
year = 2010,
pages = {137--154},
}

and it comes out looking like this (in my .bbl file):

\bibitem{ref}
{\sc Last, F., and First M.~Last, I.}
\newblock Insert Title Here
\newblock {\em Int. J. Comput. Sci 1}, 1 (2010), 137--154

As you can see, there are two problems:

1. The second name is not formatted in the style of the first
2. The second author has been replaced by their grandparent (!) (the III has been replaced by I).
   

This is using the acm.bst style file. I tried using plain.bst, and the problem persists: the second author is listed as III First M. Last.

I tried standard tricks like enclosing the III in braces, placing commas in certain places, removing them etc. No luck.

Carnival of Mathematics

First there was the Tangled Bank, and then Philosophia Naturalis. Now we have the prosaically named Carnival of Mathematics, a round up of all the mathy goodness in the blogosphere. Your 'umble blogger has an entry or two, but more importantly, there are lots of interesting posts from blogs I had never heard of before. Time to update those blogrolls !

Have all ideas already been thought of ?

Amidst a superb reflection by Jonathan Lethem on ideas, the marketplace, and copyright, consider this section, on ownership of ideas:

Undiscovered public knowledge emboldens us to question the extreme claims to originality made in press releases and publishers' notices: Is an intellectual or creative offering truly novel, or have we just forgotten a worthy precursor? Does solving certain scientific problems really require massive additional funding, or could a computerized search engine, creatively deployed, do the same job more quickly and cheaply? Lastly, does our appetite for creative vitality require the violence and exasperation of another avant-garde, with its wearisome killing-the-father imperatives, or might we be better off ratifying the ecstasy of influence—and deepening our willingness to understand the commonality and timelessness of the methods and motifs available to artists?

The "ecstasy of influence": what a beautiful way to describe the joy of illumination when we read a beautiful theorem, or a profoundly elegant idea, and use it to build something of our own.

SoCG results out

45/139 acceptances (Congratulations, David) for a 32.3% acceptance rate. Nope, no one's getting tenure with that number :)

The list will be up shortly. Since I was on the committee, I am loathe to make specific comments about papers that I liked. Suffice it to say that I am looking forward to going to Korea.

Update (7/702): And here it is.

The Geometry of Morality

From Indexed, via BB: What do the diagonals of the seven deadly sins represent ?

Some good news on funding the NSF

As has been reported in many places, the House has passed a new spending bill that puts back many of the American Competitiveness Initiative funding that was proposed for FY07. This bill was passed in agreement with the Senate, so Senate passage is hopefully forthcoming next week, when it's taken up there.

There are some differences in the level of the increase. According to Peter Harsha at the CRA blog,

Under the agreement, NSF would receive a 6 percent increase, slightly below the 7.8 percent increase called for in the ACI, but $335 million more than FY 2006.

But according to the AAAS funding update,

The National Science Foundation (NSF) would receive the full requested increase of 7.7 percent or $334 million for its core Research & Related Activities (R&RA) account to $4.7 billion. This funding would allow most research directorates to reverse declining funding of recent years with increases of between 6 and 8 percent. Total NSF R&D would climb 7.0 percent to $4.5 billion within a total budget of $5.9 billion, reversing two years of cuts in 2005 and 2006

Of course, the President still has to sign the bill. But since the ACI was his idea, one can be hopeful.

Visiting Barbados

The SoCG PC meeting was held this year at the Bellairs Research Institute in Barbados, in conjunction with a joint McGill-INRIA workshop on limited visibility, organized by Hazel Everett, Sylvain Lazard, and Sue Whitesides. It was my first time in Barbados; people have been coming to such workshops every year for many years now, and there's a nice core group of people who know how the system works and where all the good eating and drinking joints are.

Bellairs is a fairly minimally equipped research facility, smack bang on the beach on the Caribbean (i.e nicer) side of Barbados - shared dorm rooms, common bath areas, common kitchen, and the like. The facilities are much more basic than say, Dagstuhl, but this is more than made up for by the beauty of the surroundings (Did I mention that it was smack bang on the beach?). In fact, if you walk a few steps from the gate of the Institute, you end up on the beachfront of a swanky nearby hotel, which is rumored to have rooms that cost $700/night, with a 14 night stay guaranteed.

The communal aspect of the facilities (everyone cooks, we all make breakfast together, people share in the costs for food, beer, rum, rum, rum, and more rum) makes the workshop a rather friendly place. I was only there a few days alas, but the mere notion of a schedule where you work in the morning, take the afternoon off, and reconvene after dinner seems so natural, that I was wondering whether we could actually do this at SoCG or other conferences.

The workshop starts off with people proposing all kinds of problems loosely organized around the theme of limited visibility, and then people go off into self-organized groups to work on whatever seems interesting. Every now and then, there's a public review session to discuss progress. This model works surprisingly well, and all kinds of nice puzzles pop out of the discussions.

It's a great environment to do relaxed research in; not having the internet for a few days made looking up results a little tricky, but it was manageable. My main regret in leaving early: I didn't get a chance to go to the (in)famous Rocky's Bar.

A pentagon problem

Prove or disprove:

There exists no pentagon in the plane all of whose lengths (sides and diagonals) are rational.

Passed on to me by a friend. And no, I don't know the answer.

One fact that is known: no regular pentagon in the plane can have integer coordinates.

Paper ? what's paper ?

True episode:

I was looking for a paper in the university online journal listing. It's a SIAM paper published prior to 1997, so LOCUS is where it resides. Unfortunately, our online journal listing didn't seem to have LOCUS, and so I clicked on one of the help buttons to talk to a librarian (on live chat). A few minutes later, she points out to me that this particular issue of the journal is physically available in our math library.

Till that point, it had not even occurred to me to check the physical stacks.

p.s I'm just back from the CG PC meeting and the McGill workshop on limited visibility in Barbados. I had to leave early, so discussions continue. Barbados (and later, Bellairs itself) was off the internet till I left on Monday, so I have a collection of posts that will dribble out over time.

It could be one of my students...

A posting on comp.theory:

I just started a new class recently and am in need of a good class
project.
The course is a graduate course in computational geometry.
I think I will like this course but, overall, I don't find myself too
much interested in teh material
I figure a good project will help motivate me through the course and,
well, a project is required anyway! :)
My main interests are in number theory and cryptography.
Any suggestions for a nice little project that could be done in the
span of several weeks by a beginning graduate student? The idea could
either be theoretical or an implementation in code or perhaps a bit of
both.

I have to ask: how does this person know they will like the course if they are not interested in the material ?

Designing homeworks

I'm teaching CG this semester, and it's a lot of fun to go back and read some of the older texts and papers. Preparata and Shamos is actually quite a neat book, chock full of useful tricks and techniques; if only they had better ways of describing their algorithms ...

The real challenge is designing good assignment problems, and I've almost given up on this. With the number of courses available on the web, and the amount of information accessible via Google, I'm hard pressed to write down a question that can't be solved using Google and a few keywords. Even the trick of digging up interesting lemmas from related papers doesn't work if you mention the paper in class. Or maybe I'm underestimating my students' potential desire to solve the problem themselves.

And this is a problem how ?

On Harvard's search for a new president:

The growing financial importance of research also could pressure Harvard to tap a scientist, something it hasn't done since 1933.

But Harvard also could go the other way -- picking a nonscientist who could rise above turf battles and reassure the rest of the school that America's oldest and richest university isn't becoming a giant science lab.

I don't get it. Being a giant science lab is a BAD thing ?

Football and dynamic programming

We don't need no stinkin' longest common subsequence ! We'll use FOOTBALL to explain dynamic programming:

The footballcommentary.com Dynamic Programming Model is intended to provide guidance for certain decisions that arise during a game, such as two-point conversions and going for it on fourth down. This article explains the main ideas of the Model in simplified form. [...]

The Model is built around the idea that in making decisions, we are trying to maximize our team's probability of winning the game, and the opponents are trying to minimize that probability. There are three types of situations, called states, in which the Model explicitly evaluates our probability of winning. The first type of state is when one team or the other has just gained possession. The second type is when a team has just scored a touchdown, but has not yet tried for the extra point (or points). The third type is when a team is about to kick off.

Jobs at McGill

'Tis the season.

McGill University is looking to hire in geometric computing and bioinformatics. I can think of at least three reasons for any new Ph.D to apply:

* It's Canada ! Everyone gets funded by the government ! Need I say more ?
* It's in Montreal: where else can you get the feeling you're in a strange dream where you're in Paris but everyone speaks English ?
* You can "do research" in Barbados whenever you like, and definitely in the winter.

and most importantly,
* they have a job opening for people who do geometry for a living. How civilized is that ?

The Hotel Pennsylvania

Us conference goers are an ornery lot. We remember the disastrous under-construction DC hotel for SODA 2001, the bizarrely smelling Miami hotel for FOCS 1997, and the strange San Francisco hotel with the low ceilings and no lounge space for SODA 1998. There's an urban legend that FOCS can never go back to Las Vegas because of some unspecified incidents that happened in 1993; the truth is probably far more boring.

Special opprobium is reserved for the Hotel Pennsylvania in NYC, where FOCS 1999 was held. This was an old hotel; very, very old. It had the kind of rooms you'd describe as "charming" or "quaint" in publicity material. We all know what that means.

SODA 2009 is slated to be in NYC, assuming that votes are not mysteriously erased from Hal's Powerpoint slides. I am happy to announce that the Hotel Pennsylvania will in all likelihood NOT be one of the candidates for hosting the conference: it is being demolished to make way for a multi-story office complex (story via BB)

AT&T Labs is Hiring

After many years of dormant recruiting policies, and after finally getting rid of some deadwood, AT&T Labs is now hiring, in multiple areas. There's recruiting across the board in multiple areas: almost all the mentioned areas have algorithmic angles to them. So now that your faculty job applications have all been sent, send your resume to AT&T.

And in case all the mergers and rebrandings confuse you, Stephen Colbert is here to help.

Computing the size of a convex hull

We know that in the comparison model, computing a planar convex hull takes Ω(n log n) time (or Ω(n log h, if you're picky) in any reasonable algebraic decision tree model. The proof (at least for n log n) is a simple reduction from sorting. There's a more involved proof by Yao that shows that even generating the set of vertices of the convex hull takes at least n log n time. (i.e ordering the vertices isn't the only hard part). Yao's proof is on the quadratic test model; tests on objects are allowed to be signs of quadratic polynomials, and such tests characterize all known convex hull algorithms. [Addendum: Ben-Or generalizes these results to higher-degree algebraic tests as well]

My question is: is it known whether estimating the size of the convex hull is also lower bounded by n log n (or n log h) in this model ? It seems like this should be true: I don't see an obvious way of using a size-estimation oracle to actually compute the hull (or its vertices) in linear time, but I don't know if there's a proof of this. Yao's proof doesn't appear to yield any direct insight into this question.

It's worth pointing out in the light of recent results by Chan, (and by Pătraşcu on point location), that we can solve the 2D convex hull problem in sub- n log n time; we pick our favorite machine model and sort the x-coordinates in sub-n log n time, and then run the Graham scan in linear time. Chan's paper achieves sub n log n bounds for the 3D convex hull and related problems.

SODA 2007: Day 2: Da Bidness

I am sorry to say that the business meeting was so dull we couldn't even muster up the energy to argue about old controversies, let alone create new ones. Here are some of the highlights:

• Attendance was 276, comparable to SODA 2004 in New Orleans. 96 students
• 796 distinct accepted authors, from 29+ countries.
  
• Milan Ružić was awarded the best student paper prize for "Making Deterministic Signatures Quickly".
• The domain gmail.com had a 44% acceptance rate, compared to yahoo.com's 14% acceptance rate. Yahoo's stock price fell 3% on hearing this news. Google's stock price fell 5% on worries that researchers were wasting their time writing papers.
• Manufactured abstract from a random selection of words in accepted paper abstracts:
  

We present arbitrary coinciding factors that are hierarchical and use predecessors as well as important jobs. We show there exist revenues that are treasure sales and independent for identical parametric desires.

• Hal Gabow makes some attempts to shake things up with suggestions about pandering to the discrete math community, prompting this from Ian Munro:

"The notion of a discrete math community is an interesting one and somewhat perverse"

• He tries to resurrect short papers, prompting this, from an unnamed PC member (but we know who you are:))

"Please don't exhume this dead horse just to kick the rotting bones around. Again"

• SODA 2008 is in San Francisco; Shang-Hua Teng is chair.
• Major discussion on locations for SODA 2009. Three candidates emerge (NYC/Puerto Rico/Las Vegas). After an attempt at vote-rigging that would put Diebold to shame, the organizers do a straight vote and NYC wins !!

There will be no SODA Day 3 summary from me; I have to leave early to teach. The joys of professorhood !!

SODA 2007: Day 2

David has been posting detailed impressions of specific papers. Do check them out.

He mentions the constant-degree expander result of Alon, Schwartz and Shapira. I was at that talk today morning, and it's a very neat result. Expander graphs have a long and fascinating history (see the Linial-Wigderson course notes for details), and I won't try to summarize it here. Basically, the goal for a long time has been to construct reasonably sparse, constant degree expanders that also have "simple" proofs of expansion. Many of the constructions to date were either non-constructive (like the random expanders) or had very sophisticated proofs of expansion. Luca Trevisan had two very detailed posts that give an idea of how complicated some of these arguments can be.

The main contribution of the Alon/Schwartz/Shapira paper is the explicit construction of an expander that is both small (constant degree) and which has a "simple" proof of expansion. I should mention that the celebrated zig-zag product of Reingold-Vadhan-Wigderson already does this. However, their proof (and basically all proofs of expansion) rely on the spectral analysis of the graphs, using the relation between expansion and the gap between the first and second eigenvalues of the adjacency matrix of a graph.

This paper uses a graph product called a replacement product, and presents an elementary (i.e combinatorial) proof that the replacement product of two expanders is also an expander. With that in hand, they construct three graphs, and with two replacement products, get a constant-degree expander.

The invited talk today was by Monika Henzinger, of Google and EPFL. This talk was the "applied" talk (SODA usually has one such); Monika talked about algorithmic success stories at Google, discussing PageRank (and HITS), detecting document duplicates, and load balancing queries on servers. Each of these topics deserves a post on their own (the work on detecting duplicates has some particularly elegant ideas), so I don't want to go into detail here.

There's a point worth making here. The success of PageRank and other methods for search is really a success story for algorithmic modelling, rather than algorithms per se.

What do I mean by this ? I mean that the key success of PageRank, to take an example, was the idea that pages could be viewed as nodes, and edges as transitions in a Markov chain, and that relevance (or PageRank) could be modelled as a kind of "return probability". Of course, once you do this, all your theoretical machinery kicks in, and you can prove bounds on convergence, design fast algorithms, etc. But the main step was the modelling step, where you took the raw data (web pages) and viewed them in a certain abstract framework. For those of you who don't remember this, the existing paradigm of search at the time was text-based IR, and Altavista was the main exemplar of this. What Google was proposing was a very different way of viewing documents and the problem of relevance.

This is a common, and yet widely misunderstood, aspect of doing "applied" algorithms. You can define all kinds of problems, and write all kinds of papers proving results about these problems. But the mathematical tools developed for solving these problems will always take a backseat to the essentially scientific question of whether the problems and models fit the data correctly or not.

There are many domains where this is not true; cryptography is one domain where provable guarantees are not just nice, but are the crucial element of a secure system. But the success of algorithms in Web search come not from knowing to simulate a Markov chain efficiently, but from realizing that web documents are essentially nodes in a gigantic graph, and that the problem of ranking pages can be translated to a mathematical abstraction on graphs. As an aside, one of the things that the Kleinberg/Tardos textbook appears to do well is walk students through the process of problem abstraction, via the extended real-world exercises.

Understanding this aspect of data modelling changes the questions somewhat. The issue now is not, "Is this the most efficient algorithm for the problem", but rather, "Is this the right problem for the data" ? The first question will become relevant only when the second one is answered satistfactorily, more akin to a scientific discovery of truth than a mathematical one.

Outtakes:

• (Thanks to Vijay Kumar) You could, at some point, buy a watch on Amazon.com for the heavily discounted (50% off) price of $499,999. The comments on the product page are hilarious.
• What's the title of Britney Spears' only SODA paper ? "Stable Marriage is Hard"
  

SODA 2007: Day 1

I didn't always know I wanted to do algorithms; in fact, I came to Stanford thinking I was more interested in AI. One of my most embarrassing moments in graduate school was when I went to talk to my advisor-to-be. He told me he worked in the design and analysis of algorithms, and I asked him if he did design or analysis.

(Note to graduate students everywhere; when someone tells you that no question is a stupid question, don't believe it)

But after attending Philippe Flajolet's talk today on "Analytic Combinatorics", and after hearing Luc Devroye's talk yesterday, I'm not so sure that my question was off the mark.

A bit of background. What we refer to as "the analysis of algorithms" is usually associated with Don Knuth and the Art of Computer Programming. It referred to the initial methods being developed to analyze structures like hash tables, search trees and the like. Most computer scientists have taken some kind of discrete math class, and have seen the Knuth-Graham-Patashnik "Concrete Mathematics" textbook, and much of the content (basic combinatorics, recurrence relations, generating functions, etc) was used for early algorithm analysis.

These methods were quite precise. It's not uncommon to look back at papers from the 70s and see detailed constants in front of running times for algorithms; Bob Sedgewick mentioned one such calculation in his introduction to Flajolet's talk. People didn't use O() notation like a sledgehammer, the way we do today.

Over time, we became more comfortable with O() notation; algorithms became more sophisticated, and it became harder to figure out actual constants. It didn't seem to matter as much. After all, when you were coming up with elaborately complicated algorithms that ran in exotic times like O(n^(11/7)), it hardly seemed to matter what the constant was. This was, and has continued to be, the Age of Design.

But all along, with people like Flajolet, Knuth, Sedgewick, and many many others, the work of really analyzing algorithms continued on. ANALCO is an offshoot of this long effort; a way to attract people working on some of the considerably hard problems in this area, while creating some cross-fertilization with the design crowd at SODA. Of course, by no means do I claim that algorithm designers don't analyze; of course we do. But it's fair to say that the sophisticated analysis methods and sophisticated design methods do appear to have diverged.

Which brings us to the talk today. The rough theme for his talk was an overview of how the combinatorial problem of counting structures (trees, steps in a linear probe, etc) can be transformed into a generating function, to which then the methods of real, and more recently, complex analysis can be applied. There's some pretty heavy mathematical machinery being thrown out here: we saw large deviation theory in yesterday's talk, for example, and there are things Flajolet talked about that I have only the barest inkling of.

Doing such analysis is hard; it's not as if we're suddenly going to abandon O() notation. But, as Piotr Indyk pointed out when we discussed this later, computers aren't getting any faster, and data is getting larger and larger, and it's more and more true that the actual constants in front of a running time matter, sometimes even more than the asymptotic bound. If more sophisticated analysis methods allow us to reveal algorithm running times more transparently, this also helps repair some of the "bad press" theoreticians can get with more applied folk.

So the analysis of algorithms takes on its original meaning again; there is a conference as well, now in its 13th year, and there's an upcoming book by Flajolet and Sedgewick that covers much of the mathematics Flajolet refers to in his talk. I looked at it briefly (it's 753 pages and counting!), and I hope that when it does come out, we learn more about how to use methods from analytic combinatorics to improve analysis techniques for even our run-of-the-mill algorithms.


Outtakes:

• I've quite enjoyed the talks I've attended thus far. I haven't written much about them, but that's mostly due to laziness on my part. I've been quite torn having to navigate the multiple parallel sessions; human cloning, where art thou ?
• [From a random research paper session] It's funny to see a speaker struggling with their desire to display EVERY SINGLE SLIDE that they made, when faced with a remorseless clock ticking down to zero. Word of advice: no one really cares if you go through all your slides, or even flip thru them frantically while muttering very fast. They do care if you go over time and drag things ON and ON and ON.
• Contrary to the general confusion being spread around, the wireless DOES work and it IS free.
  
• I don't like hotels with two towers; especially when I'm in one and the conference is in the other, and ESPECIALLY when the only connection between the two towers is at the lobby.
  

SODA 2007: Day 0

Getting into New Orleans at 1 am because of "mechanical trouble" meant that I haven't been at my best so far. But I've already heard one amazing talk today.

Luc Devroye gave the ANALCO plenary lecture on "Weighted Heights of Random Trees", based on work with his students Erin McLeish and Nicolas Broutin. After having sat through many talks with titles like this, I generally approach them with great caution and with a clear escape route. But...

This was an amazing exposition of a topic that could have become dry and terse, and essentially incomprehensible, within a slide or two. He had jokes, (that were funny), a global plan for the material, enough technical material that I went away feeling like I'd learnt something, and intuition galore. And the work itself is very beautiful.

So what was it all about ? The problem is really quite simple to state. Suppose I give you a (random) weighted binary tree, where nodes attach to parents randomly, and edges may have weights chosen randomly. What is the maximum height of such a tree ?

The standard application for such a tool is in analyzing binary search trees. The height of a such a tree controls the running time of an algorithm that needs to use it. And there's now a vast literature analyzing both the asymptotics of the height distribution (basically it's sharply concentrated around 2 log n) and the specific constants (the maximum height of a random binary search tree is roughly 4.3 log n, and the minimum is around 0.37 log n).

The "master goal" that Devroye described in his talk was this: Suppose I have a general way of attaching nodes to parents (that leads to a general distribution on subtree sizes), and a general way of attaching weights to edges (rather than being deterministically 1 for binary search trees). Such a general model captures the analysis of tries (trees on strings that are very important in text searching), geometric search structures like k-d trees, and even restricted preferential attachment models in social network analysis (Think of the edges as hyperlinks, and the height of the tree as the diameter of a web tree).

Is there a generic theorem that can be applied to all of these different situations, so that you can plug in a set of distributions that describes your process, and out pops a bound on the height of your tree ? It turns out that you can (with some technical conditions). The method uses two-dimensional large-deviation theory: can you estimate the probability of a sum of random variables being bounded by some function, while at the same time ensuring that some other sum of random variables (that might depend slightly on the first) is also bounded ?

An example of a 1D large deviation result is of course a Chernoff bound. Devroye showed that a 2D large deviation bound for the height of such trees can be expressed in a similar form using the so-called Cramér exponent, something that will probably not be surprising to experts in large deviation theory. After that, the analysis for any tree process becomes a whole lot easier. You have to analyze the corresponding Cramér function for your distributions, and a bound (with a constant; no big-O nonsense here!) pops out.

He also talked about a neat extension of this method to analyzing the "skinnyness" of k-d tree decompositions, showing that for a kind of "relaxed" k-d tree construction, the skinniest cell can be extremely skinny (having a super-linear aspect ratio). It's the kind of result that I imagine would be very difficult to prove without such a useful general theorem.

Puzzles and Mysteries

"Whatever comes in sufficiently large quantities commands the general admiration." Trurl the Constructor, from Stanislaw Lem's Cyberiad.

I've been reading Malcolm Gladwell's masterful article on the Enron scandal, and he frames it with the device of 'puzzles' vs 'mysteries':

The national-security expert Gregory Treverton has famously made a distinction between puzzles and mysteries. Osama bin Laden’s whereabouts are a puzzle. We can’t find him because we don’t have enough information. The key to the puzzle will probably come from someone close to bin Laden, and until we can find that source bin Laden will remain at large.

The problem of what would happen in Iraq after the toppling of Saddam Hussein was, by contrast, a mystery. It wasn’t a question that had a simple, factual answer. Mysteries require judgments and the assessment of uncertainty, and the hard part is not that we have too little information but that we have too much. The C.I.A. had a position on what a post-invasion Iraq would look like, and so did the Pentagon and the State Department and Colin Powell and Dick Cheney and any number of political scientists and journalists and think-tank fellows. For that matter, so did every cabdriver in Baghdad. [....]

If things go wrong with a puzzle, identifying the culprit is easy: it’s the person who withheld information. Mysteries, though, are a lot murkier: sometimes the information we’ve been given is inadequate, and sometimes we aren’t very smart about making sense of what we’ve been given, and sometimes the question itself cannot be answered. Puzzles come to satisfying conclusions. Mysteries often don’t.

There is a fundamental problem that comes up when you start messing with "data". Our training in algorithms makes us instinctively define a "problem" when working with data, or any kind of applied domain. Many of the problems in clustering, like k-center, k-median, k-means, or what-have-you, are attempts to structure and organize a domain so we can apply precise mathematical tools.

In a sense, we treat these problems like puzzles to be solved. The game is then to find the best solution, the fastest, the most accurate; but the structure of the puzzle has been set. We can change the game (and we often do), but once again, the goal is to crack the puzzle.

But when you get down and dirty with data, you start seeing the problems that Gladwell describes. If your goal is to "understand" the data, then more is not necessarily better, and causes more confusion, and what you need is interpretative skills, rather than number-crunching or even problem solving skills.

This is what makes data mining so hard and exasperating, and yet so important. The need is clearly there, and there are mysteries to mine. But we've been attacking data mining problems as puzzles, and realizing fairly quickly that solving a puzzle doesn't reveal the mystery of the data.

I've often likened data mining research to an ooze; it's thin and spreads horizontally, without too much depth. But I think that's because the puzzles that we solve are of limited range, and not terribly deep. What we seem to need more are interpretative frames rather than algorithmic frames; frames that tell us about invariances in the data, rather than about quirks of representations.

I'm moving to academia

(WARNING: personal information ahead. If you prefer to think of the Geomblog as written by robotic monkeys pounding on millions of keyboards, read no further)

One of the reasons the Geomblog has been silent these past few weeks is that I've been busy moving, and falling sick, and unpacking, and unpacking, and unpacking, and...

Now, where was I ?

Oh yes, moving. After many years of cloistered comfort at AT&T, I've decided to take the plunge into the exciting and dangerous waters of academia, at the University of Utah (30, count 'em, 30 minutes from the best powder skiing imaginable).

Why the move ? Many people have asked me this, and the answer is actually simple: because I finally wanted to. AT&T has been a wonderful place for me to work (and they're hiring next year, so get those applications ready), but I realized that the kinds of things I wanted to do (teach, initiate my own research programs, guide students, and participate in the academic conversation in general) were better done at this point in a university setting.

It's not a decision I made easily. It is said that the real value of a workplace is in the colleagues you have, and from that point of view, leaving AT&T has been hard. Leaving for a real job after completing a Ph.D felt like a natural rite of passage, much as leaving India for grad school felt like. But leaving the labs was a purely elective decision, and as such makes the transition a little more jarring.

And now here I am, in Salt Lake City (technically, I'm in Cincinnati airport waiting for a much delayed flight to New Orleans, but I digres...), preparing for my geometry class, working on a proposal, and doing my research. On the one hand, I have the basic day to day business of research more or less under control, and work and collaborations go on seamlessly. On the other hand, I often feel like a fresh Ph.D at his first job, managing myriad things that seem new and foreign. It's a strange feeling.

But I'm genuinely excited to be teaching, and am looking forward to interacting with students; something that I sorely missed at AT&T, except for the occasional summer. It will be an exciting adventure.

Three thoughts on Anatoly Vershik's article...

Via Peter Woit and Luca Trevisan comes a pointer to an article by Anatoly Vershik in the new Notices of the AMS, lamenting the role of money prizes in mathematics. Three thoughts:

• "the newspapers, especially in Russia, are presently “discussing” a completely different question: Is mathematical education, and mathematics itself, really necessary in contemporary society ". At the risk of sounding patronizing, I find it terribly worrisome that the place that spawns such amazing mathematicians, and has such a legendary training program for scientists, should even indulge in such a discussion. Especially now, with all the handwringing in the US about the lack of mathematical training at school level, it seems a particularly bad time to abdicate what is a clearly a competitive advantage.
  
  
• He talks about not understanding "the American way of life" as regards how money is viewed. There's a juxtapositon of images that I've always been struck by, and that tennis lovers will recognize: At Wimbledon, the winner is crowned with a fanfare, royalty, and a trophy (or plate); the prize money is never really discussed. At the US Open on the other hand, along with the fanfare comes the huge check handed out by some corporate sponsor while the PA blares out the amount. The trophy presentation, although making for good photo-ops, seems almost anticlimactic.
  
  I am a little skeptical though whether offering prizes like the Clay prize convinces people that mathematics is a lucrative profession. After all, this hasn't happened for the Nobel prizes.
  


• On the false-duality: I've heard a variation of this argument many times. It goes basically like this: "Either you're interested in subject X and don't need motivation, or you aren't, in which case no amount of motivation is going to help". This is possibly true for identifying students likely to make the transition to being professionals in subject X. In fact, I've heard an anecdote from the world of music, about a maestro who would tell all his students that they would fail professionally at being musicians. His argument was that only the ones who cared enough to prove him wrong had what it took to survive.
  
  One has to realize though that the teaching of a subject is not about creating Mini-Mes: only a small fraction of the students we come in contact with will become professional computer scientists/mathematicians/whatever. But a large fraction of these students will vote, many of them will go onto position of influence either in industry or government, and they will all contribute to a general awareness of the discipline. So it's a mistake to give up on motivating students; even if they never end up proving theorems for a living, a better appreciation for those who do will help all of us.
  

Categories:

• outreach

Sorting algorithm animations

Pat Morin has a great collection of Java sorting applets. You can line up three at a time and have them sort a random permutation of one through N. It's fun to see insertion sort or bubble sort earnestly plodding along long after merge sort or quick sort has blazed through.

Categories:

• teaching

Author ordering and game theory.

There are typically two major ways of ordering authors on a paper. In theoryCS, we (mostly) use the lexicographic ordering (by last name); in many other areas, author ordering by relative contribution is common. There are variants: advisors might list themselves last by default even within a lexicographic or contribution-based system, and middle authors may not always be ordered carefully, etc etc.

Since paper authorship conveys many important pieces of information, author ordering is an important problem. It's an even bigger problem if you have hundreds of authors on a paper, some of which may not even know each other (!). This is apparently becoming common in the HEP (high energy physics) literature, and an interesting article by Jeremy Birnholtz studies the problem of authorship and author ordering in this setting. The study is sociological; the author interviews many people at CERN, and derives conclusions and observations from their responses.

As one might imagine, not too many of the problems of 1000-author papers are translatable to our domain. After all, these papers are bigger than our conferences, and I doubt anyone has never needed a "publication committee" when writing their paper. And yet, the interviews reveal the same kinds of concerns that we see all the time. Is a certain ordering scheme shortchanging certain authors ? Did a certain author do enough to merit authorship ? Who gets to go around giving talks on the work ?

Towards the end of the paper, the author makes an interesting (but unexplored) connection to game theory. The players in this game are the authors, and what they are trying to optimize is perceived individual contributions by the community (the "market"). Intuitively, lexicographic ordering conveys less information about author contributions and thus "spreads" contributions out: however, it's not symmetric, in the sense that if we see a paper with alphabetically ordered authors, it could be a product of a truly relative contribution ordering that yields this ordering, or a lexicographic ordering. In that sense, authors with names earlier in the alphabet are disadvantaged, something that seems counter-intuitive.

As it turns out, there's been some work on the equilibrium behaviour of this system. To cite one example, there's a paper by Engers, Gans, Grant and King (yes, it's alphabetically ordered) that studies the equilibrium behaviour of author ordering systems with a two-author paper in a market. Their setup is this:

• The two players A and B decide to put in some individual effort.
  
• The relative contribution of each (parametrized by the fraction of contribution assigned to A) is determined as a (fixed but hidden) stochastic function of the efforts.
• The players "bargain" to determine ordering (lexicographic or contribution). The result is a probability of choosing one kind of ordering, after which a coin is tossed to determine the actual ordering
  
• The work is "published", and the market assigns a value to the paper as a whole, and a fraction of this value to A, based on public information and other factors.

Now all of these parameters feed back into each other, and that's where the game comes from. What is a stable ordering strategy for this game ? It turns out that lexicographic ordering does yield equilibrium behaviour, and contribution-based ordering does not.

What's even more interesting is that if we look at merely maximizing research output (the external "quality" of the paper), then this is not maximized by lexicographic ordering, because of the overal disincentive to put in more effort if it's not recognized. However, this does not suggest that always using contribution-based ordering is better; the authors have an example where this is not true, and one intuition could be that if there's a discrepancy between the market perception of contribution and individual contributions, then there is a disincentive to deviate too much from the "average" contribution level.

It's all quite interesting. Someone made a comment to me recently (you know who you are :)) about how assigning papers to reviewers made them value research into market-clearing algorithms. I like the idea of applying game theory to the mechanisms of our own research.

(HT: Chris Leonard)

Previous posts on author ordering here, and here.

Categories:

• community