[home]

Thore Husfeldt

Papers

Finding a path of superlogarithmic length Andreas Björklund and Thore Husfeldt.
SIAM J. Computing. Vol. 32 (2003), No. 6, pp. 1395–1402. [PDF]
Announced at Proc. 29th ICALP 2002, Springer LNCS 2380, pp. 985-992. [DVI, PS, PDF]

Lower bounds for approximate polygon decomposition and minimum gap. Joachim Gudmundsson, Thore Husfeldt, and Christos Levcopoulos.
IPL 81(3), 2002, pp. 137-141. [PDF]

A cell probe lower bound for dynamic nearest-neighbour searching. Stephen Alstrup, Thore Husfeldt and Theis Rauhe.
Proc. 12th SODA 2001, pp. 779-780. [PS.GZ]

Marked Ancestor Problems. Stephen Alstrup, Thore Husfeldt and Theis Rauhe.
Proc. 38th FOCS 1998, pp. 534-543. [PS.GZ]

New lower bound techniques for dynamic partial sums and related problems. Thore Husfeldt and Theis Rauhe.
SIAM J. Computing. Vol. 32 (2003), No. 3, pp. 736–753. [PDF]
A preliminary version appeared as Hardness Results for Dynamic Problems by Extensions of Fredman and Saks’ Chronogram Method in Proc. 25th ICALP 1998, Springer LNCS 1443, pp. 67-78. [.dvi], [.ps.gz], [.pdf]

Lower Bounds for Dynamic Transitive Closure, Planar Point Location, and Parentheses Matching. Thore Husfeldt, Theis Rauhe, and Søren Skyum.
Nordic Journal of Computing 3(4):323-336, Winter 1996. Prelim. version in Proc. 5th SWAT 1996, Springer LNCS 1097, pp. 198-211. [PS.GZ]

Fully Dynamic Transitive Closure in Plane Dags with One Source and One Sink. Thore Husfeldt.
Proc. 3rd European Symposium on Alorithms (ESA), 1995, Springer LNCS 979, pp. 199-212. [PS.GZ]

Dynamic Algorithms for the Dyck Languages. Gudmund Skovbjerg Frandsen, Thore Husfeldt, Peter Bro Miltersen, Theis Rauhe, and Søren Skyum.
Proc. 4th Workshop on Algorithms and Data Structures (WADS), 1995, Springer LNCS 955, pp. 98-108. [PS.GZ]

A Communication Complexity Proof that Symmetric Functions have Logarithmic Depth. Gerth Stølting Brodal and Thore Husfeldt.
BRICS Report RS-96-1, 1996. [PS.GZ]

[home]