Machinations


Generating Functionology
May 31, 2010, 6:41 pm
Filed under: Uncategorized | Tags: , ,

During the summer theory seminar for my research group, I like to cover a topic that is mathematically challenging, but not something that any of us would normally learn about in the course of our day-to-day research.  This summer, we’re working through the book generatingfunctionology by Herbert Wilf , a mathematician at U. Penn.  This book has the marvelous succinctness of many great math texts, while somehow being more accessible and even periodically having a wry sense of humor (the “snake oil method”?).  Divide and conquer is one of the most powerful approaches we have for solving problems in CS (whereby divide and conquer I mean: recursion, induction, recurrence relations, etc.).  This book extends the applicability of that approach.

Plus, the book is free! A fully functional pdf is available at the above web page.



End of Semester

The end of the semester here at UNM just about killed me. In addition to the usual academic hubbub, I hosted a visitor, submitted a paper, finished up the camera ready for our PODC paper, and dealt with my toddler who decided it would be a good couple of weeks to wake up every night at 2am (teething?, headache?, likes a dose of cherry-flavored children’s tylenol as a nightcap?)

The camera-ready of our paper, “Breaking the O(n^2) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary” (that I blogged about previously) is now available here.  This was probably the most time I’ve spent going from an accepted paper to a camera ready – mostly because the algorithm in the paper consisted of several small parts with many connections between the parts.  Hopefully, our new version makes everything much easier to understand.

Some great news we received, right after submitting the camera ready, is that our paper was selected to be in the “best paper session” of PODC.  The list of all such papers is below – I know that at least some of these papers will be invited to a special issue of the JACM, and all of them look interesting.   The best paper session is a new thing for PODC.  I definitely like the idea of having multiple best papers, it gives more information about the assessment of the PC than a single best paper.  I’ll probably read through most of these before the conference.

Deterministic Distributed Vertex Coloring in Polylogarithmic Time
Barenboim, Elkin

Breaking the O(n^2) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary
King, Saia

Optimal Gradient Clock Synchronization in Dynamic Networks
Lenzen, Kuhn, Locher, Oshman

Online set packing and competitive scheduling of multi-part tasks
Emek, Halldorsson, Mansour, Patt-Shamir, Radhakrishnan, Rawitz

How to Meet when you Forget: Log-space Rendezvous in Arbitrary Graphs
Czyzowicz, Kosowski, Pelc

A Modular Approach to Shared-memory Consensus, with Applications to the Probabilistic-write Model
Aspnes

Constant RMR Solutions to Reader Writer Synchronization
Bhatt, Jayanti