## Saturday, June 24, 2006

### FREE REPRINTS

Bill Gasarch is giving away free copies of one of our papers. Get them while they last.

I recently got in the postal mail REPRINTS of a recently published article of mine. This used to be standard—when an article was published you got 50 free copies. Less and less journals do this now.

Are reprints needed anymore?

YES: When someone visits you in your office its nice to be able to give them a copy without having to print it out. Also, when I went up for Tenure and Full Prof, I was asked for 14 copies of every article I ever wrote, so it was good to have the preprints around. (some went to my letter writers, which makes sense, some went to the committee deciding my case, which makes less sense, some went to the dean, provost, and for all I know the governor of Maryland, which makes no sense. Well maybe its okay–the governor has a Ph.D. in Mathematics–it was on Recursive Algebraic Topology. I am, of course, kidding–there is no such field.)

Even before the electronic age I never used reprints much (except when I went up for promotion). And the last few times I've written a letter for promotion I was NOT given the set of papers (NOTE: It would have been an appreciated courtesy if they had).

The article A Tight Lower Bound for Restricted PIR Protocols by Beigel, Fortnow and Gasarch (Computational Complexity, Vol 15, No 1, 2006, 82-91) can be YOURS if you send a Self-Addressed Stamped Envelope to

William Gasarch
Dept of Computer Science
University of Maryland
College Park, MD 20742
USA

(I would bet $5.00 I won't get any takers, except that someone may take the bet and request a copy, thus gaining$4.61)

1. Wouldn't the gain of the bet only be $4.22? 2. Wouldn't it be nice if one day a promotion case came in the form of a nice card, explaining that the accompanying CD (or DVD) includes a letter requesting your critique of a fellow faculty member, whose papers, wedding video clip, recent chest X-Rays, and credit report could all be found in the enclosed disk? 3. I can't resist pointing out that Recursive Algebraic Topology may be a sensible thing to study. Apparently, modern algebraic topology makes heavy use of things called Grothendieck universes, which are rather hefty objects from a logical perspective (they're a bit stronger than, say, the consistency of ZFC set theory), particularly when they're used (like with Fermat's Last Theorem) to prove statements about ordinary arithmetic. There's some debate among proof theorists at the moment about whether those principles could be eliminated from the proof so that, say, FLT could be proven in something like Peano arithmetic. (After all, it would be rather interesting if a straightforward statement like FLT were independent of Peano arithmetic.) Such work would almost inevitably include asking which principles of algebraic topology are not only arithmetic, but computable...that is, Recursive Algebraic Topology. My points being...give it five years, and there might be such a field. 4. (I would bet$5.00 I won't get any takers, except that someone may take the bet and request a copy, thus gaining $4.61) So, find a mechanism (in the game-theoretic sense), such that if no one really wants a copy, the person you are betting against will get 5.00$, but such that it won't be worth it for that person to send a request himself. If you know the identity of the better, then that is easy.

You could always bet that there won't be 2 people interested in a reprint. But then the better can recruit a friend.

5. You could always bet that there won't be 2 people interested in a reprint. But then the better can recruit a friend.

Then he could just bet $5 that 7 people won't be interested in a reprint, because then the counter betters would be out$0.46 from the whole deal.

6. My question is, can the prng-based technique for pir with 2 counterparties be generalized to k counterparties, and if it can does the recurrence multiply by 2 at each recursive application to get from n^(1/x) to n^(1/(x+1)), or does it multiply by k? That result would be very nearly practical.

It's surprising how poorly that recurrence works when you plug in real numbers. n^e my ass. It's a good example of how the scale of the real universe actually matters.

7. BTW, FOCS results are out.

8. BTW, FOCS results are out.

Is there a published list of accepted papers?

9. Also, anyone care to comment why it took two weeks after the PC meeting to get the notifications out?

10. Again FOCS results are very hostile to algorithmic papers.

11. Again FOCS results are very hostile to algorithmic papers.

Anecdotal evidence is awesome!

I have discovered that FOCS is against papers written on airplanes, *but only if you had an aisle seat*. My papers written in window seats were both accepted.

12. Regarding paper prints... I am against it for the sake of environment.
If we have a soft copy we can take print-out when (and only when) necessary. I am a theoretician and I use recycled paper to do my theory work. I also stopped all my paper bills and pay all my bills online.

13. Anecdotal evidence is awesome! I have discovered that FOCS is against papers written on airplanes, *but only if you had an aisle seat*. My papers written in window seats were both accepted.

A minor difference is that a lot of people have reached the conclusion that FOCS is not algorithms friendly, while you are the only one who has ever posited the aisle seat hypothesis.

14. A minor difference is that a lot of people have reached the conclusion that FOCS is not algorithms friendly, while you are the only one who has ever posited the aisle seat hypothesis.

The previous commenter was clearly basing their assertion on the fact that their paper(s) were not accepted to this FOCS, as opposed to e.g. basing their conclusion on an analysis of the full accepted papers list.

15. While I am at least somewhat sympathetic to the old "FOCS/STOC is anti-algorithms" claim, the FOCS 2006 PC has a lot of algorithms researchers. This makes it a bit tough to blame the complexity researchers this time.

16. The previous commenter was clearly basing their assertion on the fact that their paper(s) were not accepted to this FOCS,

This is pure speculation on your part. Not an unlikely guess but far from self-evident as you claim.

17. the FOCS 2006 PC has a lot of algorithms researchers.

Using a functional definition in terms of papers published in algorithms conferences, the FOCS PC has about four full time algorithmers, plus another five or so half time algorithmers.

IMHO, the mere fact that four out of 23 PC members is considered "a lot of algorithms researchers" suggests that there is an anti-algorithms bias.

This makes it a bit tough to blame the complexity researchers this time.

This is a move in the right direction.

18. This is pure speculation on your part. Not an unlikely guess but far from self-evident as you claim.

It's not "pure" speculation by far- either their interpretation is correct, or the initial commenter is a disgruntled FOCS'06 PC member. The former seems more likely.

19. IMHO, the mere fact that four out of 23 PC members is considered "a lot of algorithms researchers" suggests that there is an anti-algorithms bias.

Ahh, now it's clear. If your interpretation of algorithms is so narrow then "algorithms" do indeed deserve a smaller representation in the conference.

On the other hand, the rest of us recognize that

Andrews
Arora
Charikar
Chawla
Erickson
Fleischer
Kannan
Kaplan
Karlin
Racke
Rajaraman
Spielman

form a very large contigent of people known (and more often than not, well-known) for their work in algorithms (and I even left off the MCMC people!)

20. either their interpretation is correct, or the initial commenter is a disgruntled FOCS'06 PC member.

There are other not so unlikely possibilities, e.g.: the person who made the comment is currently attending an algorithms workshop. Today, at lunch, the subject of FOCS results came out and it turned out there were several other well known algorithmers who submitted papers to FOCS this year and all got rejected.

Another scenario is that griper belongs to a prestigious CS department with several top notch algorithmers. Again, over lunch today it came out that none of their papers got accepted.

21. Andrews
Arora
Charikar
Chawla
Erickson
Fleischer
Kannan
Kaplan
Karlin
Racke
Rajaraman
Spielman

This list is ridiculous. Let's say, to grab a random example, look at Christos. He has spend the last n years doing high quality computational game theory, and the previous n years before that doing top notch complexity theory. Along the way he published five papers (out of 272) in SODA and 2 in ESA.

Under such liberal classification rules, a researcher who published one paer out of 20 in, say, databases, would qualify as a DBer. Clear nonsense.

22. Somehow Christos seems like a poor choice for your argument--everything he does is about algorithms; even his complexity is driven completely by algorithmic questions. He is perhaps the single most algorithmically-minded person I know.

Your criteria are silly (and it's precisely because most of his algorithmic work is published in the "anti-algorithmic" STOC/FOCS...) I'll just list my favorite CHP algorithms papers of the last 10 years

An Approximation Scheme for Planar Graph TSP

On the k-Server Conjecture

Computing correlated equilibria in multi-player games

23. -everything he does is about algorithms; even his complexity is driven completely by algorithmic questions.

I wouldn't go as far as saying _everything_ he does is algorithmic, but I can grant you the overall sentiment. Yet, doing algorithmic inspired complexity theory makes you an applied complexicist, not an algorithmer.

I would call your list of people "algorithmic friendly" researchers as opposed to algorithmers.

24. I meant to say:

I would call some in your list of people "algorithmic friendly" researchers as opposed to algorithmers.

25. I have not submitted a paper to FOCS nor am I a member of the PC. I haven't seen the list of accepted papers either. However, the griping I am reading seems particularly overblown and baseless. The complaints about the composition of the PC are absurd and reflect ignorance more than anything. Isn't it just possible that the accepted papers are simply stronger or more innovative?

26. Isn't it just possible that the accepted papers are simply stronger or more innovative?

It is possible, and frankly with a more balanced committee this year it is not too unlikely.

At the same time it is rather self-serving to dismiss a complain that has been echoed by many people across many different periods as simply "[awesome] anecdotal evidence".

27. Forget about algorithms - how about crypto?! Only one crypto researcher on the PC this year (Kilian), and with all due respect to Kilian (whom I deeply respect) he hasn't been all that active in crypto for the past 5 years.

In general, many fewer crypto papers are accepted to FOCS/STOC than algorithms papers. Whether one agrees with this bias or not, it makes it hard for theoretical cryptographers when comparing their pulication lists to algorithms researchers.