Papers

Some papers

• Controlled grammatic ambiguity. ACM Transactions on Programming Languages and Systems 16 (3), 1994, 1024 - 1050. Unfortunately, the published version hides all mathematics in an electronic appendix. This includes, for example, a transfinite proof of correctness. A full version is found here.
• Firing Games . Technical Report DIKU-TR-94/15.
• On the Approximability of Numerical Taxonomy. (With Agarwala, Bafna, Farach, Paterson, and Narayanan) Univerisity of Warwick, Computer Science Reseach Report CS-RR-330. Preliminary version presented at SODA'96. Accepted for SICOMP.
• On RAM Priority Queues . Presented at SODA'96.
• Structured Programs have Small Tree-Width and Good Register Allocation . Presented at WG'97.
• To Provide or To Bound: Sampling in Fully Dynamic Graph Algorithms (with Henzinger). A preliminary version Improved sampling with applications to dynamic graph algorithms was presented at ICALP'96.
• Static Dictionaries on AC0 RAMs: Query time O(sqrt(log n/loglog n)) is necessary and sufficient (with Andersson, Miltersen, and Riis). Presented at FOCS'96.
• A pragmatic implementation of monotone priority queues (with Andersson). From the DIMACS'96 implementation challenge.
• Randomized sorting in $O(n\log\log n)$ time and linear space using addition, shift, and bit-wise boolean operatations . DIMACS Technical Report 96-14. Presented at SODA'97.
• Decremental dynamic connectivity . Presented at SODA'97.
• Undirected Single Source Shortest Paths in Linear Time. Presented at FOCS'97.
• Floats, Intergers, and Single Source Shortest Paths. To be presented at STACS'98.
• Faster deterministic sorting and priority queues in linear space . Max Plank Institut fur Informatik Technical Report MPI-I-97-1-016. To be presented at SODA'98.
• Poly-logarithmic deterministic fully-dynamic graph algorithms I: connectivity and minimum spanning tree. (with Jacob Holm and Kristian de Lichtenberg) Technical Report DIKU-TR-97/17.
• Poly-logarithmic deterministic fully-dynamic graph algorithms II: 2-edge and biconnectivity. (with Jacob Holm and Kristian de Lichtenberg) Technical Report DIKU-TR-97/26.