Limits on The Number of Co-Authors?
Limits on the number of co-authors for conference papers
Craig Venter is not a theorist, but is a famous biologist. He led one of the teams that sequenced the human genome. Here is a list of his co-authors from their famous paper — The Sequence of the Human Genome.
I do wonder how they decided on the author order—more on this in a moment.
The biology paper has many more authors than we ever see in theory papers, but that is changing now. The rise of the polymath projects of Tim Gowers and Terry Tao and others has caused some interesting issues to be raised. For a polymath paper who is the author, and where should their names appear? Mike Mitzenmacher also has recently raised the question of who should be a co-author.
Today I want to talk about an unimportant issue: what is the most number of authors possible on a paper accepted to a major theory conference? Sometimes I need to not have a serious topic, and today is such a day.
This quest for an upper bound is in the best spirit of theory research. Note, the lower bound seems clear:
In our research area the order of authors is usually decided by the alphabetic order. Some papers mention this explicitly, so it is clear the order is not meaningful. The other day I ran into one of our faculty from robotics, Tucker Balch. As he introduced me to his mom who was visiting, he said:
“I should have been a theorist”.
I guess in robotics they do not always use alpha-order.
Seymour Ginsburg and Sheila Greibach wrote many many papers together on various aspects of language theory. It was always “Ginsburg and Greibach,” since they used, as most did then, the alpha-order rule. Sheila told me for one paper she really wanted to be the first author—she never explained exactly why. Perhaps she felt she did way more than half the work, or just for once she wanted it to be “Greibach and Ginsburg.” But Seymour was adamant and would not budge from the alpha-rule. Eventually, Sheila won: the paper appeared in STOC 1972 as,
Sheila Carlyle-Greibach, Seymour Ginsburg, Jonathan Goldstine: Uniformly Erasable AFL’s.
She used her full name.
Years before polymath projects I thought about proving upper bounds on the number of authors possible in a theory paper accepted at a conference. I worked with a number of others—too numerous to mention today—on how to prove these bounds. Here are a few of the bounds we could prove:
Population: It is always good to start with an easy bound. Our first idea was to use the total world population as an upper bound. Surely a paper could have at most the total number of people in the world as the total number of authors. This gives a bound of according to the World Bank today.
To be even safer it might be important to include all people who have ever lived at any time in history. This is estimated at 106 billion by Carl Haub. This seems like a very strong argument, although the bound obtained is quite large.
Page: We assumed a page limit on the length of the paper and a lower bound on the allowed font size. Since all papers in conferences, at the time, had all authors listed in the beginning, this yields a much better upper bound on the number of authors. The number of authors is easily seen to be bounded by
where is the page limit and is the maximum number of characters per page. The factor of arises from the following lemma:
Lemma: If there are authors, then the author list uses at least characters.
Proof: The author list must look like this:
Assuming each author’s name is at least one character, then the bound follows.
Later this was improved by assuming that authors also had to have their email addresses included. Since all the authors could be at the same institution this yielded a bound of
where This follows from a simple argument: the email list could be
Note, we assume that authors’ names could be a single letter. There has been some work on improving this lemma by arguing that author names cannot all be a single letter. Others have argued that author names should be from a random distribution. While I like these results, they make stronger assumptions, and this reduces the strength of their upper bounds.
Powerpoint: The same argument above using the page limit can be used, only now we assume that all authors must fit on the first powerpoint slide. Making reasonable assumptions about visibility of the slide yields very strong bounds. I do not recall the exact bounds; perhaps someone can work out the details.
Speaking: This is my favorite bound. In the introduction of each paper, we assume the session chair must read the names of all the authors. Given a 20 minute limit on a presentation, the reading of the list of names must be at most the total time for the talk. Thus, the number of authors is determined by how fast one can say all the names.
It is important to note we do not allow session chairs to say:
All the authors have the same name and it is “”
Each author, even if all have the same name, deserve the recognition of having their name read aloud.
The key parameter here is how fast can a person speak. Books on tape are read at less than 200 words per minute. This translates into a bound of probably about authors as a maximum. This, of course, leaves no time for the actual presentation, but of course at least all the authors get said aloud.
Are these bounds the best possible?