HEINZ NIXDORF INSTITUTE



Computer Science Department


Algorithms and Complexity

Christian Sohler


Home
Research
Courses
Publications



















Christian Sohler


Christian Sohler - Publications:
2005:

  • Gereon Frahling, Piotr Indyk, Christian Sohler
    • Sampling in Dynamic Data Streams and Applications
    Accepted at the 21st Annual ACM Symposium on Computational Geometry (SoCG), 2005.

  • Gereon Frahling, Christian Sohler
    • Coresets in Dynamic Geometric Data Streams
    Accepted at     the 37th ACM Symposium on Theory of Computing (STOC), 2005.

  • Marcin Bienkowski, Valentina Damerow, Friedhelm Meyer auf der Heide, Christian Sohler
    • Average Case Complexity of Voronoi Diagrams of n Sites from the Unit Cube
    Accepted at the     21th European Workshop on Computational Geometry, 2005.

2004:
  • Jens Krokowski, Harald Räcke, Christian Sohler and Matthias Westermann
    • Reducing State Changes with a Pipeline Buffer
    Accepted at Vision, Modelling, and Visualization 2004 (VMV'04).
  • Valentina Damerow, Christian Sohler
    • Extreme Points under Random Noise
    Accepted at the 12th Annual     European Symposium on Algorithms (ESA'04).

  • Vikas Bansal, Friedhelm Meyer auf der Heide, Christian Sohler
    • Labeling Smart Dust
    Accepted at the 12th Annual     European Symposium on Algorithms (ESA'04).

  • Artur Czumaj, Christian Sohler
    • Sublinear-Time Approximation for Clustering via Random Sampling
    Accepted at the 31st     International Colloquium on Automata, Languages and Programming (ICALP), 2004.

  • Artur Czumaj, Christian Sohler
    • Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
    Accepted at the 36th ACM Symposium on Theory of Computing (STOC), 2004.

  • Valentina Damerow, Christian Sohler
    Smoothed Number of Extreme Points under Uniform Noise
    Accepted at the 20th European Workshop on Computational Geometry, 2004.

2003:
  • Christian Sohler 
    • Property Testing and Geometry
    Dissertation, HNI-Verlagsschriftenreihe, Vol. 119, Heinz-Nixdorf Institut and University of Paderborn,  2003.

  • Valentina Damerow, Friedhelm Meyer auf der Heide, Harald Räcke, Christian Scheideler, Christian Sohler
    Smoothed Motion Complexity
    In: Proceedings of the 11th Annual European Symposium on Algorithms (ESA'03).
  • Micah Adler, Harald Räcke, Naveen Sivadasan, Christian Sohler, Berthold Vöcking
    • Randomized Pursuit-Evasion in Graphs (extended abstract)
    Combinatorics, Probability & Computing 12(3), 2003.
    Extended abstract at the 29th International Colloquium on Automata, Languages and Programming  (ICALP'02).
2002:
2001:
2000:
  • Artur Czumaj, Christian Sohler, Martin Ziegler
    Property Testing in Computational Geometry
    In: Proceedings of the 8th Annual European Symposium on  Algorithms (ESA'00), Saarbrücken, pages 155-166.
  • Christian Sohler, Martin Ziegler
    • Computing Cut Numbers
    In: Proceedings of the 12th Canadian Conference on Computational Geometry (     CCCG '00)

1999:
1997: