# WADS accept list, and two new arxiv uploads

The list of accepted papers for WADS 2007 has been posted to the conference web site.

I have two papers there (out of three submissions): "Edges and switches, tunnels and bridges", with Marc van Kreveld, Elena Mumford, and Bettina Speckmann, and "Space-efficient straggler identification in round-trip data streams via Newton's identities and invertible Bloom filters", with Mike Goodrich.

The streaming straggler paper also just became available at the arxiv. The problem involves handling a large sequence of checkin and checkout requests, most of which are expected to be matched in pairs, and determining from them a much smaller set of mismatched requests. If the only kind of mismatch is a checkin without a checkout, we have an algebraic solution with optimal space; for more general sequences of requests we have a randomized algorithm with slightly more space, and a proof that no deterministic solution is possible (essentially the only thing you can do is to map the group Z^n, representing the numbers of requests for each id, down to a smaller group, and any group map will have a nontrivial kernel that forces you to confuse a perfectly matched request sequence with a mismatched one).

Also new on arxiv: On Verifying and Engineering the Well-gradedness of a Union-closed Family. A new paper (unrelated to WADS) with J.-C. Falmagne and H. Uzun, on testing whether the union-closure of a set family contains enough sets that you can connect every pair of sets in the closure by a short path of insertion and deletion operations, always staying within the closure. This path-connectedness is important for the computerized learning systems of Falmagne's company (Uzun's employer) because it translates to the condition that one can learn a set of concepts one at a time without running into cyclic dependencies in their prerequisites.

I'm hoping that the edge and switch paper can be made online soon as well, but it's not there yet. It's about drawing edge crossings in graphs as over-under relationships, and choosing whether to go over or under at each crossing in order to improve the readability of the drawing.

I have two papers there (out of three submissions): "Edges and switches, tunnels and bridges", with Marc van Kreveld, Elena Mumford, and Bettina Speckmann, and "Space-efficient straggler identification in round-trip data streams via Newton's identities and invertible Bloom filters", with Mike Goodrich.

The streaming straggler paper also just became available at the arxiv. The problem involves handling a large sequence of checkin and checkout requests, most of which are expected to be matched in pairs, and determining from them a much smaller set of mismatched requests. If the only kind of mismatch is a checkin without a checkout, we have an algebraic solution with optimal space; for more general sequences of requests we have a randomized algorithm with slightly more space, and a proof that no deterministic solution is possible (essentially the only thing you can do is to map the group Z^n, representing the numbers of requests for each id, down to a smaller group, and any group map will have a nontrivial kernel that forces you to confuse a perfectly matched request sequence with a mismatched one).

Also new on arxiv: On Verifying and Engineering the Well-gradedness of a Union-closed Family. A new paper (unrelated to WADS) with J.-C. Falmagne and H. Uzun, on testing whether the union-closure of a set family contains enough sets that you can connect every pair of sets in the closure by a short path of insertion and deletion operations, always staying within the closure. This path-connectedness is important for the computerized learning systems of Falmagne's company (Uzun's employer) because it translates to the condition that one can learn a set of concepts one at a time without running into cyclic dependencies in their prerequisites.

I'm hoping that the edge and switch paper can be made online soon as well, but it's not there yet. It's about drawing edge crossings in graphs as over-under relationships, and choosing whether to go over or under at each crossing in order to improve the readability of the drawing.